RSAP是一种非对称加密算法，我将其简化为三个参数：
公共模数$ n的比特大小$ n $ p = c \ qdot q $；
私钥模数$ p $的比特大小$ \ kappa $ ;
奇数公共指数$ e $。
对于密钥生成，它是用$ \ gcd（p-1，e绘制一个随机的$ \ kappa $位素数$ p $ ）= 1 $;以及一个随机素数$ q $，使得$ N = p \ cdot q $具有$ n $位，而$ \ gcd（q-1，e）= 1 $。公用密钥为$（N，e）$，如RSA中所示。它是预先计算的$ d = e ^ {-1} \ bmod（p-1）$ [在标准RSA中为$ dp $]。私钥为$（p，d）$。除了消息最多只能为$ \ kappa-1 $位的限制外，裸RSAP中的加密与裸RSA中的加密相同：$ C = M ^ e \ bmod N $。解密使用$ M = C ^ d \ bmod p $。之所以可行，是因为$ C = M ^ e \ bmod N $意味着$ C \ equiv M ^ e \ pmod p $，这意味着每个Fermat小定理都意味着$ M \ equiv C ^ d \ pmod p $，并且认为$ M <2 ^ {\ kappa-1}
RSAP的主要优点是解密比RSA快得多：与具有相等大小的两个素数$ n / 2 $的RSA CRT实现相比，速度提高了$ \ approx 2（{n \ over2 \ kappa}）^ 3 $ [该指数采用经典的乘法算法]。当使用与我们的参考值相同的模数（$ \ kappa = n / 2 $）时，速度至少快两倍。最高可提高$ \ approx250 $（对于$ n = 5000，\ kappa = 500 $，这是原始RSAP文章中考虑的积极参数化）。
裸RSAP容易遭受灾难性攻击（在除了那些困扰裸露的RSA加密的加密算法之外：如果与对手泄露的密文$ C $相对应的明文$ M $，则可以考虑$ N $（从而损失所有安全性）；例如，如果$ M $是密文$ C =（2 ^ {\ kappa}）^ e \ bmod N $的明文，则$ p = 2 ^ \ kappa-M $（注意，选择$ C $可确保表示相应的$ M $最多具有$ \ kappa-1 $位）。
一个明显的改进（在SPAKE中考虑，但由于不被证明是不安全的）在加密之前使用了随机填充，如RSAES -OAEP或OAEP +，但经过参数化后除外，以便填充的消息$ \ tilde M $的比特数少于$ \ kappa $，而在RSA中的比特数少于$ n $；并在解密之后执行相应的冗余检查，然后再使用（并可能释放）解密后的消息（甚至比RSA还要多），要求对填充进行解密的检查一定不能泄漏有关填充错误的信息，例如通过时间差异）。
对于参数化的具体示例：$ n = 2048，\ kappa = 576，e = 17 $，使用SHA-1哈希对576位填充RSAES-OAEP模数，我们可以传输240位消息（填充到576位$ \波浪号M $并加密为2048位密码$ C = \波浪号M ^ e \ bmod N $），但解密速度比10倍快具有标准2048位模数的RSA-CRT中，并且希望与之等效的安全性。
问题：
理论上（与实现无关的）攻击是否比考虑模数更有效？
我们可以在某些假设下用填充证明RSAP的安全性吗？
什么是实现攻击和适当的对策？
对于给定的$ n $，我们可以降低$ \ kappa $多少？
我没有进行其他一些调整和注意事项：
为了减小公共密钥证书的大小，对于某些参数$ \ lambda $，可以预先确定$ N $中的$ n- \ lambda $比特或根据持有人的身份来确定比特。在Shamir的RSAP和SPAKE / ALIKE中就是这种情况。
用$ \ gamma <\ kappa $（而不是$ \ gamma = \ kappa-1 $），可以将求幂的消息减少为$ \ gamma $位（而不是$ \ gamma = \ kappa-1 $
最低$ e $取决于$ n $和$ \ gamma $；根据Shamir和我对SPAKE / ALIKE的理解，$ e> 2n / \ gamma $似乎是安全的。
当对手可以获取非常多的公共密钥并且对任何密钥都感到满意时，我们可能需要采取额外的预防措施；我会让其他人提出一个单独的问题，允许对此进行讨论。
#1 楼
参数。修复正整数$ \ kappa $，例如896或1024； $ n \ ggg \ kappa $，例如2048或3072；对于112位或128位安全级别，分别使用奇数$ e> n /（\ kappa-1-192）$，例如3或5。将一个随机的oracle $ H \冒号\ {0,1，\ dots，2 ^ {\ kappa-1}-1 \} \修复为\ {0,1 \} ^ {256} $，例如SHA-256。 （长度是固定的，因此不会发生长度扩展攻击。）
密钥生成。
用$ 2 ^ {\ kappa-1}
发件人。
给出$ N $，随机选择整数$ 0
接收器。
在收到$ y $后给出$ p $，计算出最小的非负数$ x'\ equiv y ^ d \ pmod p $其中$ d $解决$ ed \ equiv 1 \ pmod {p-1} $，并在键$ H（x'）$下打开AEAD消息。
正确性。
$ \ newcommand {\ divides} {\ mathop {\ vert}} $
由于$ p \ divide N $，所以等价$ y \ equiv x ^ e \ pmod N $意味着$ y \ equiv x ^ e \ pmod p $。因此，根据欧拉定理，$$ x'\ equiv y ^ d \ equiv（x ^ e）^ d \ equiv x ^ {ed} \ equiv x \ pmod p，$$因为$ \ phi（p）= p-1 $和$ ed \ equiv 1 \ pmod {p-1} $。并且由于发送方选择了$ x <2 ^ {\ kappa-1}
安全性。
$ \ newcommand {\ Z} {\ mathbb {Z}} \ newcommand {\ divides} {\ mid} \ newcommand {\ ndivides} {\ nmid } \ newcommand {\ given} {\ mathrel {|}} $
让$ A \冒号\ Z ^ + \ times \ Z ^ + \成为\ Z ^ + $是尝试解密的随机算法$ x'= A（N，y）<2 ^ {\ kappa-1} $。如果$ x'= A（N，y）= y ^ d \ bmod p $，则$ A $成功，且成功概率为$ \ Pr [x'= A（N，y）= y ^ d \ bmod p] $ 。
用$ F [A]（N）= u-u'$定义随机算法$ F [A] \冒号\ Z ^ + \ to \ Z $，其中$ u \ sim U [2 ^ {\ kappa-1 }，2 ^ \ kappa）$，$ v = u ^ e \ bmod N $，而$ u'= A（N，v）$，因此$ u \ equiv v ^ d \ bmod p $。如果$ F [A]（N）= p $，则此算法成功。
如果$ u \ leq p $，则没有$ 0
因此
\ begin {align *}
\ Pr [F [A]（N）= p]
＆= \ Pr [A（N，v）= v ^ d \ bmod p，p
$ p的概率
此归约法剩下的遗漏部分是集合$ \ {x ^ e \ bmod N：2 ^ {\ kappa-2} \ leq x <2 ^ {\ kappa-1} \} $与集合$ \ {u ^ e \ bmod N：2 ^ {\ kappa-1} \ leq u <2 ^ \ kappa \} $，因此可以想象，始终适用于前者的解密算法可能永远无法适用于后者。目前尚不清楚我们如何更改$ x $和$ u $的范围以强制解密算法同时工作，因为在不知道$ p $的情况下$ x $的整个点都将低于$ p $，并且在不知道$ p $的情况下，$ u $的整个点都将高于$ p $。另一方面，任何在$ e ^ \ mathit {th} $取模$ N $的根超过$ p $的整数上以某种方式持续失败的算法都可以转换为通过二进制搜索找到$ p $的算法调用费用约为$ \ kappa $，而不是一个调用。
如果我们填写了缺失的部分，那么我们可以证明，可以为任意$ H $一般解密消息的对手可以将$ N $分解为因素，而付出的额外努力可以忽略不计，而且概率更低。
使用随机Oracle $ H $是至关重要的：泄露有关$ x $的任何信息都会破坏安全性。
发送者统一选择$ x $也是至关重要的：如果$ x <\ sqrt [e] {N} $，则最小非负$ y \ equiv x ^ e \ pmod N $实际上是$ y = x ^ e $，因此对手只能计算实数$ \ sqrt [e] { y} $以恢复$ x $。限制$$ x <\ sqrt [e] {N} <\ sqrt [e] {2 ^ n} = 2 ^ {n / e} \ leq 2 ^ {\ kappa-1-192} $$的概率通过$ 2 ^ {\ kappa-1-192} / 2 ^ {\ kappa-1} = 2 ^ {-192} $，因为$ x $在$ [0，2 ^ {\ kappa-1}中的整数之间均匀分布）$。即使一万亿用户都对四方消息进行加密，一次发生的可能性也可以由可忽略的$ 2 ^ {-100} $来限定。
我们还可以通过安全级别对其进行参数化，或者如果我们总是选择$ x $高于$ 2 ^ {\ kappa-2} $，则可能将其驱为零，在这种情况下，我们可以放松$ e $使其仅高于$ n /（\ kappa-1）$。但是对于结构化消息，还可能需要担心其他攻击。
成本。
发送方必须在恒定时间内计算一个$ n $位的模幂。对于$ e = 3 $，这仅需要一个$ n $位的模平方和一个$ n $位的模乘；对于$ e = 5 $，需要两个平方和一个乘法。
接收器必须在恒定时间内计算一个$ \ kappa位的模幂。
密钥封装在$ n $位中。
警告：大多数bignum库在整个恒定时间内都是不好的，即使是那些应该更了解并且应该对此感到不满意的东西，如OpenSSL。
答案。
攻击比分解容易吗？如果可以通过安全性降低来弥补安全性降低的程度，则可以将任何以成功概率$ p_0 $和成本$ C $从RSAP-KEM恢复封闭密钥的算法扩展为具有成功概率$ p_0的分解算法。 / 3 $并花费$ C $加上一个$ \ kappa位减法。
是否减少了安全性？也许！
有实施攻击吗？毫无疑问，很像普通的RSA。我强调了一个明显的问题：很难找到好的恒定时间任意模数模幂。
对于给定的$ n $，我们可以降低$ \ kappa $多少？根据我对最佳（量子前）因子分解算法的了解，ECM确定$ \ kappa $的下限，其运行时间是$ \ kappa $的函数，而$ n $的下限由NFS，其运行时间是$ n $的函数。 （后量子分解的故事部分由pqRSA解决，后者考虑了RSAP但未使用它。）
从ECM性能的实验证据推算得出，其成本约为$ \ exp（0.9 \ sqrt {2 \ log 2 ^ \ kappa \ log \ log 2 ^ \ kappa}）$标量乘法；启发式地将三个位相加，因为标量乘法每次至少要花费8位操作；并四舍五入为2的乘方之和-信封的背面计算得出$ \ kappa = 512 $的最高80位安全级别，$ \ kappa = 768 $的100位安全级别的估计。 ，$ \ kappa的112位安全级别= 896 $和$ \ kappa的128位安全级别= 1024 $。
这些是上限：如果您也选择$ n $小巧的智能攻击者将使用NFS代替ECM。从NFS性能的实验证据中寻找和推断，以估计安全级别的上限（作为$ n $的函数），留给读者练习。
注意事项：Crypto.SE不是一本受同行好评的学术密码学期刊。我可以凭着自己的声誉声名起任何想要的东西，而不会给我的任职期带来不利影响。您有责任确保这是正确的！
评论
$ \ begingroup $
如果您仔细观察，我所做的就是将您对“灾难性攻击”的先见之见改编为一种通用技术，以将解密预言转化为分解算法。然后使用随机预言机来密封交易，使其成为安全的公钥密钥封装机制！
$ \ endgroup $
–吱吱作响的s骨
17年8月26日在15:50
$ \ begingroup $
嗯，是的。以最多一位安全为代价，我们可以修复$ \ gamma = \ kappa-1 $并要求$ 2 ^ {\ kappa-1} + 2 ^ {\ kappa-2} $ \ endgroup $
–吱吱作响的s骨
17年8月29日在12:35
$ \ begingroup $
我尝试使还原更加严重，以容许解密算法在$ 2 ^ {e \ kappa} \ bmod N $上失败。我发现了一个更严重的问题：尚不清楚$ x \ sim U [0，2 ^ {\ kappa-1}] $在$ x ^ e \ bmod N $上的分布是否与$ u ^ e上的分布一致\ bmod N $表示$ u \ sim U [2 ^ {\ kappa-1}，2 ^ \ kappa）$。 （当然，这并不意味着它不是一个不安全的KEM！只是减少对分解的处理无法达到我希望的方式。实际的安全性可能与RSA-KEM相同，但性能更高。）
$ \ endgroup $
–吱吱作响的s骨
17年8月29日在15:26
$ \ begingroup $
我完全同意上面的最后一句话（以及大部分答案）。
$ \ endgroup $
–fgrieu♦
17年8月29日在15:55
评论
可以将裸RSAP应用于随机选择的对象，并使用该对象的随机oracle的$ \ hspace {.68 in} $值作为密钥，尽管这种方法会增加密文开销。 $ \ hspace {.96 in} $@Ricky Demer：是的。 SPAKE / ALIKE使用让人联想到的东西（填充的消息是随机的，然后用于构建AES-128密钥，并使用该密钥对零进行加密）。看到幻灯片，它们很有趣。
对于上一个项目符号中引用的设置，可能最好在指示$ r ^ e $和模数的对中使用随机预言值，而不是仅使用$ r ^ e $。 $ \; $
@Ricky Demer：我很难理解你在上面的评论。它是否指的是对手可以获取许多公钥或其他东西的环境？什么一对？
仍然是一个有趣的问题，您在此方面取得了任何进展吗？请注意，也可以考虑使用PACE-CAM进行双重身份验证（SPAKE似乎仅提供芯片身份验证）。