我需要重新生成EC私钥（可以通过特殊方法构造），使用尽可能少地存储信息。在不损害针对详尽搜索的安全性的前提下，少于128位是不可能的。
我很好奇我是否可以使用以下方法：
生成一个随机的128位值。这是我将存储以重新创建私钥的值。
使用随机值的256位哈希（例如SHA256）作为私钥。 （我有一种做到这一点的方法，不会使任何密钥偏向任何其他密钥。）
相应的公共密钥将被公开。
因此，我可以从中重新生成私有密钥128位值。在我看来，私钥和128位值应该与为私钥使用随机256位值并将其存储一样安全。穷举搜索显然是不切实际的，并且EC密钥的属性不应该能够从公钥或通过散列向后退。原则上，EC搜索空间减少了一半，但似乎没有任何切实可行的方法可以利用此功能。
我缺少什么吗？有什么理由不能像存储完整的256位密钥一样安全吗？假设潜在的对手知道公钥和算法。对手的目标是获取私钥。在我看来，这显然和基础算法一样安全，但是我知道的程度足以使我不相信自己。
#1 楼
您的建议是正确的。这是一种显示方法：在完全实现的签名系统中（非对称加密的情况类似），共有三个模块：
密钥对生成器，生成伪随机密钥对；
签名生成器，使用私钥对某段数据生成签名；
签名验证器，对某段数据进行签名验证
密钥对生成器是确定性算法是可以接受的，只要它“具有强大的加密能力”并在“足够长的”秘密种子上工作即可。 “足够长”表示：如果必须达到$ 2 ^ t $的安全级别，则长度至少为$ t $位的字符串。
您建议的是简单地存储PRNG种子而不是存储PRNG种子。密钥对生成器的输出。每次要使用私钥时，您都再次运行PRNG。由于PRNG是确定性的，因此产生的签名与您存储私钥时获得的签名完全相同，因此从外部看，这与“常规”设置没有区别。因此具有安全性。
该概念适用于任何非对称算法，而不仅仅是基于EC的算法。您可以使用RSA这样的方法，例如使用PRNG重新生成素数$ p $和$ q $。但是，对于RSA而言，代价会很高（生成私钥比实际计算签名要昂贵得多），并且生成过程容易受到定时攻击的部分泄漏，因此这会有些微妙。对于DSA，Diffie-Hellman或ElGamal之类的算法或其EC变体，私钥只是给定$ q $（组顺序）取模的随机值，因此速度很快。
唯一棘手的一点是，当您只需要256位伪alea时，表明“一次SHA-256调用”是合适的，具有加密功能的PRNG。在随机预言模型中，没有问题。在实际的标准合规性和管理接受性的世界中，您可能要使用经过批准的PRNG，尤其是HMAC_DRBG（这是NIST认为是“最强”的一种）。严格选择私钥是必需的。对于（EC）DSA，有一个私钥$ x $，并且对于每个签名，必须生成一个新的随机$ k $模$ q $。 $ k $的偏差可以忽略不计，这一点至关重要。但是对于$ x $，您可以宽容一些。例如，对于子订单阶$ q $的大小为256位或更大的曲线，它足以生成单个256位整数，并以$ q $模为单位进行减小。某些值的选择机会可能是其他值的两倍，或者，如果$ q $的大小大于256位，则某些值的选择概率为零；但这不是$ x $的问题。对于$ k $，这将是一个非常严重的问题。
评论
$ \ begingroup $
什么是“伪alea”？我见过您以前使用过该术语，但没有遇到过其他用法。
$ \ endgroup $
–PulpSpy
2012年1月12日下午16:41
$ \ begingroup $
@PulpSpy：这可能是高卢主义（即我不愿意翻译成英语的法语术语）。 “ Alea”本身是拉丁语中的“命运”或“随机性”。 “伪alea”的意思是“看起来像随机位，但是是通过具有未知种子的确定性过程生成的”。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2012年1月12日17:06
$ \ begingroup $
标准的英语术语是“伪随机”。
$ \ endgroup $
– David Schwartz
2012年1月12日19:55
$ \ begingroup $
仅供参考，PRNG的链接已更新，似乎在公众评论后不久将再次修订。以下是临时链接：SP800-90A和公共草案
$ \ endgroup $
–半比特
13-10-21在15:26
评论
命题不仅是安全的（如答案中所述），还可以通过使用有目的地的慢速密钥派生功能（例如在步骤2中使用scrypt），对I使用少于128位的数据，而不会损害针对穷举搜索的安全性；在本文定义的64ms级别，104位密钥似乎与SHA-256抵御碰撞一样安全。