动机
从未见面的发送者和接收者仍可能希望保密通信。公钥加密把加密所需的信息与解密所需的信息分开。RSA 的两个运算都使用模幂运算;其算术正确性可以严格证明,但真实实现是否安全还需要更多分析。下列小数值仅用于展示计算过程。
定义
对整数 a , b a,b a , b 和正整数 n n n ,若 n n n 整除 a − b a-b a − b ,记 a ≡ b ( m o d n ) a\equiv b\pmod n a ≡ b ( mod n ) 。a a a 的剩余类是所有与它同余的整数。加法、乘法和非负整数次幂保持同余:把一个整数换成与它同余的整数,运算结果的剩余类不变。若存在 v v v 使 u v ≡ 1 ( m o d n ) uv\equiv1\pmod n uv ≡ 1 ( mod n ) ,称 u u u 模 n n n 可逆。贝祖(Bézout)等式说明,这当且仅当 gcd ( u , n ) = 1 \gcd(u,n)=1 g cd( u , n ) = 1 。
选择不同素数 p , q p,q p , q ,令 N = p q N=pq N = pq 、φ = ( p − 1 ) ( q − 1 ) \varphi=(p-1)(q-1) φ = ( p − 1 ) ( q − 1 ) 。此密钥生成方法假设 φ > 2 \varphi>2 φ > 2 ;此时 e = φ − 1 e=\varphi-1 e = φ − 1 是可行的选择。选择满足 1 < e < φ 1<e<\varphi 1 < e < φ 且 gcd ( e , φ ) = 1 \gcd(e,\varphi)=1 g cd( e , φ ) = 1 的 e e e 。贝祖等式给出 d d d 使 e d ≡ 1 ( m o d φ ) ed\equiv1\pmod\varphi e d ≡ 1 ( mod φ ) ,取其正代表。公钥是 ( N , e ) (N,e) ( N , e ) ,私有指数为 d d d 。此处消息用模 N N N 的剩余类 m m m 表示。原始 RSA 运算是
c ≡ m e ( m o d N ) , m ′ ≡ c d ( m o d N ) . c\equiv m^e\pmod N,\qquad m'\equiv c^d\pmod N. c ≡ m e ( mod N ) , m ′ ≡ c d ( mod N ) . 这称为教材式 RSA。它是剩余类上的确定性映射,本身还不是安全的消息加密方案。
定理/命题
定理 4.1.3
(所有剩余类上的 RSA 正确性)
若 p , q p,q p , q 是不同素数,e , d e,d e , d 是正整数,且 e d ≡ 1 ( m o d ( p − 1 ) ( q − 1 ) ) ed\equiv1\pmod{(p-1)(q-1)} e d ≡ 1 ( mod ( p − 1 ) ( q − 1 )) ,则对每个整数 m m m ,都有 m e d ≡ m ( m o d p q ) m^{ed}\equiv m\pmod{pq} m e d ≡ m ( mod pq ) ,包括被 p p p 或 q q q 整除的消息。
若不同素数 p , q p,q p , q 都整除整数 z z z ,则 p q pq pq 整除 z z z 。因此两个整数若分别模 p p p 、模 q q q 同余,则它们模 p q pq pq 同余。
证明思路
写成 e d = 1 + k ( p − 1 ) ( q − 1 ) ed=1+k(p-1)(q-1) e d = 1 + k ( p − 1 ) ( q − 1 ) 。模 p p p 考虑:若 p ∣ m p\mid m p ∣ m ,则 m e d m^{ed} m e d 与 m m m 均为零。否则,费马(Fermat)小定理给出 m p − 1 ≡ 1 ( m o d p ) m^{p-1}\equiv1\pmod p m p − 1 ≡ 1 ( mod p ) ,于是
m e d = m ( m p − 1 ) k ( q − 1 ) ≡ m ( m o d p ) . m^{ed}=m(m^{p-1})^{k(q-1)}\equiv m\pmod p. m e d = m ( m p − 1 ) k ( q − 1 ) ≡ m ( mod p ) . 交换两个素数可得模 q q q 的同余;第二个定理将它们合并为模 p q pq pq 的同余。第二个定理可由欧几里得(Euclid)引理证明:p ∣ z p\mid z p ∣ z 给出 z = p a z=pa z = p a ;因 q ∣ p a q\mid pa q ∣ p a 且 q ∤ p q\nmid p q ∤ p ,得 q ∣ a q\mid a q ∣ a ,所以 p q ∣ z pq\mid z pq ∣ z 。此证明没有假设消息与 N N N 互素。
证明透视
逐素数证明涵盖不可逆消息 假设 e d ed e d 模 ( p − 1 ) ( q − 1 ) (p-1)(q-1) ( p − 1 ) ( q − 1 ) 同余于 1 1 1 ,通过同一指数的两种分解用了两次:在 p p p 处是 k ( p − 1 ) ( q − 1 ) = ( p − 1 ) ⋅ k ( q − 1 ) k(p-1)(q-1)=(p-1)\cdot k(q-1) k ( p − 1 ) ( q − 1 ) = ( p − 1 ) ⋅ k ( q − 1 ) ,在 q q q 处是 ( q − 1 ) ⋅ k ( p − 1 ) (q-1)\cdot k(p-1) ( q − 1 ) ⋅ k ( p − 1 ) 。e e e 与 d d d 为正,使 k ≥ 0 k\ge0 k ≥ 0 ,并使 m m m 不可逆时 m e d m^{ed} m e d 仍有意义。
关键一步是每次只处理一个素数,并分成 p ∣ m p\mid m p ∣ m 与 p ∤ m p\nmid m p ∤ m 两种情形。模素数时唯一的非单位是零,而零显然不变;证明正是这样避开需要 gcd ( m , N ) = 1 \gcd(m,N)=1 g cd( m , N ) = 1 的欧拉(Euler)定理。p p p 与 q q q 互不相同只在最后用到:中国剩余步骤中的欧几里得引理把两个同余式合成一个模 p q pq pq 的同余式,论证就此收尾。
费马定理本身可这样证明:若 p ∤ m p\nmid m p ∤ m ,乘以 m m m 会置换模 p p p 的非零剩余类 1 , … , p − 1 1,\ldots,p-1 1 , … , p − 1 。把它们相乘并消去非零乘积,得到 m p − 1 ≡ 1 ( m o d p ) m^{p-1}\equiv1\pmod p m p − 1 ≡ 1 ( mod p ) 。消去合法是因为素数模下每个非零剩余类可逆;合数模下非零元素未必可逆。
反例模式
重复的素数破坏正确性 若允许 p = q p=q p = q ,同一方法会用 N = p 2 N=p^2 N = p 2 ,指数条件取模 ( p − 1 ) 2 (p-1)^2 ( p − 1 ) 2 。取 p = q = 3 p=q=3 p = q = 3 ,则 N = 9 N=9 N = 9 、( p − 1 ) ( q − 1 ) = 4 (p-1)(q-1)=4 ( p − 1 ) ( q − 1 ) = 4 ;选 e = d = 3 e=d=3 e = d = 3 ,因为 e d = 9 ≡ 1 ( m o d 4 ) ed=9\equiv1\pmod4 e d = 9 ≡ 1 ( mod 4 ) 。消息 3 3 3 给出 3 9 ≡ 0 ( m o d 9 ) 3^9\equiv0\pmod9 3 9 ≡ 0 ( mod 9 ) ,因为 9 ∣ 3 9 9\mid3^9 9 ∣ 3 9 ;连单位 2 2 2 也给出 2 9 = 512 = 56 ⋅ 9 + 8 ≡ 8 ( m o d 9 ) 2^9=512=56\cdot9+8\equiv8\pmod9 2 9 = 512 = 56 ⋅ 9 + 8 ≡ 8 ( mod 9 ) 。两者都没有还原消息。逐素数的步骤在模 3 3 3 下仍成立,但合并步骤失败:模 9 9 9 时,模 3 3 3 的同余不能确定剩余类。不同的素数是定理真正需要的假设。
例题详解
取 p = 5 , q = 11 p=5,q=11 p = 5 , q = 11 ,则 N = 55 N=55 N = 55 、φ = 40 \varphi=40 φ = 40 。取与 40 互素的 e = 3 e=3 e = 3 。因为 3 ⋅ 27 = 81 = 2 ⋅ 40 + 1 3\cdot27=81=2\cdot40+1 3 ⋅ 27 = 81 = 2 ⋅ 40 + 1 ,可取私有指数 d = 27 d=27 d = 27 。该密钥很小,仅用于展示计算。
用此密钥对 m = 7 m=7 m = 7 加密,得 c ≡ 7 3 = 343 ≡ 13 ( m o d 55 ) c\equiv7^3=343\equiv13\pmod{55} c ≡ 7 3 = 343 ≡ 13 ( mod 55 ) 。反复平方法给出 13 2 ≡ 4 13^2\equiv4 1 3 2 ≡ 4 、13 4 ≡ 16 13^4\equiv16 1 3 4 ≡ 16 、13 8 ≡ 36 13^8\equiv36 1 3 8 ≡ 36 、13 16 ≡ 31 ( m o d 55 ) 13^{16}\equiv31\pmod{55} 1 3 16 ≡ 31 ( mod 55 ) 。由于 27 = 16 + 8 + 2 + 1 27=16+8+2+1 27 = 16 + 8 + 2 + 1 ,
13 27 ≡ 31 ⋅ 36 ⋅ 4 ⋅ 13 ≡ 7 ( m o d 55 ) . 13^{27}\equiv31\cdot36\cdot4\cdot13\equiv7\pmod{55}. 1 3 27 ≡ 31 ⋅ 36 ⋅ 4 ⋅ 13 ≡ 7 ( mod 55 ) . 依次约化,31 ⋅ 36 ≡ 16 31\cdot36\equiv16 31 ⋅ 36 ≡ 16 、16 ⋅ 4 ≡ 9 16\cdot4\equiv9 16 ⋅ 4 ≡ 9 、9 ⋅ 13 ≡ 7 9\cdot13\equiv7 9 ⋅ 13 ≡ 7 。所用指数来自 27 的二进制展开。
令 m = 5 m=5 m = 5 ,它与 55 有公因数。加密得到 5 3 = 125 ≡ 15 ( m o d 55 ) 5^3=125\equiv15\pmod{55} 5 3 = 125 ≡ 15 ( mod 55 ) ;全剩余类定理仍保证 15 27 ≡ 5 ( m o d 55 ) 15^{27}\equiv5\pmod{55} 1 5 27 ≡ 5 ( mod 55 ) 。事实上,模 55 的幂依次满足 15 2 ≡ 5 15^2\equiv5 1 5 2 ≡ 5 、15 3 ≡ 20 15^3\equiv20 1 5 3 ≡ 20 、15 4 ≡ 25 15^4\equiv25 1 5 4 ≡ 25 、15 5 ≡ 45 15^5\equiv45 1 5 5 ≡ 45 、15 6 ≡ 15 15^6\equiv15 1 5 6 ≡ 15 ,从指数一开始以五为周期,故 15 27 ≡ 15 2 ≡ 5 15^{27}\equiv15^2\equiv5 1 5 27 ≡ 1 5 2 ≡ 5 。不能对 m = 5 m=5 m = 5 直接使用模 55 的欧拉定理,因为它不是可逆元。
常见错误
知道 N , e N,e N , e 是为了允许加密,并不意味着根据定义公开了两个素因子。若已知因子,可计算 ( p − 1 ) ( q − 1 ) (p-1)(q-1) ( p − 1 ) ( q − 1 ) ,再用扩展欧几里得算法求 d d d 。反向的安全断言更微妙:这里没有证明破解 RSA 与分解整数等价。正确性本身不保证安全。
原始 RSA 是确定性的:同一公钥下相同消息产生相同密文。攻击者若能猜测消息,可自行计算候选密文并比较。因此小消息空间特别容易受到这种比较。实际方案使用标准化的随机编码和实现防护;本节没有规定或实现这样的方案。不可把这里的小参数或裸模幂当成安全协议。
总结
模每个素数时分两种情况:素数整除消息时直接处理,否则应用费马定理。合并两个同余便得到对所有剩余类的正确性。密钥生成要求指数模所选的群阶倍数可逆。消息的大小与表示、随机编码和对实现攻击的防护则需要另行分析。
练习
快速检查
(取 p = 3 , q = 11 , e = 3 p=3,q=11,e=3 p = 3 , q = 11 , e = 3 ,求 N , φ N,\varphi N , φ 和一个有效的 d d d 。)
解答 · 答案 N = 33 N=33 N = 33 、φ = 20 \varphi=20 φ = 20 ,且 3 ⋅ 7 = 21 ≡ 1 ( m o d 20 ) 3\cdot7=21\equiv1\pmod{20} 3 ⋅ 7 = 21 ≡ 1 ( mod 20 ) ,所以 d = 7 d=7 d = 7 。
快速检查
(用此密钥加密 m = 4 m=4 m = 4 ,再解密。)
解答 · 答案 4 3 = 64 ≡ 31 ( m o d 33 ) 4^3=64\equiv31\pmod{33} 4 3 = 64 ≡ 31 ( mod 33 ) 。由于 31 ≡ − 2 31\equiv-2 31 ≡ − 2 ,有 31 7 ≡ ( − 2 ) 7 = − 128 ≡ 4 ( m o d 33 ) 31^7\equiv(-2)^7=-128\equiv4\pmod{33} 3 1 7 ≡ ( − 2 ) 7 = − 128 ≡ 4 ( mod 33 ) 。由定理也可得到同一结果。
快速检查
(为什么 φ = 40 \varphi=40 φ = 40 时不能选 e = 10 e=10 e = 10 并找到 e d ≡ 1 ( m o d 40 ) ed\equiv1\pmod{40} e d ≡ 1 ( mod 40 ) 的 d d d ?)
解答 · 答案 任意 10 d 10d 10 d 都能被 10 整除,不可能与 1 之差是 40 的倍数。等价地,gcd ( 10 , 40 ) = 10 \gcd(10,40)=10 g cd( 10 , 40 ) = 10 ,所以 10 模 40 不可逆。
高效求幂及其不变量
无需先算出巨大的整数 m e m^e m e 再约化。反复平方法在每次乘法后取模:初始化 r = 1 r=1 r = 1 、b ≡ m ( m o d N ) b\equiv m\pmod N b ≡ m ( mod N ) 、h = e h=e h = e 。当 h > 0 h>0 h > 0 时,若 h h h 为奇数就令 r ← r b m o d N r\leftarrow rb\bmod N r ← r b mod N ;然后令 b ← b 2 m o d N b\leftarrow b^2\bmod N b ← b 2 mod N 、h ← ⌊ h / 2 ⌋ h\leftarrow\lfloor h/2\rfloor h ← ⌊ h /2 ⌋ 。不变量是
r b h ≡ m e ( m o d N ) . r b^h\equiv m^e\pmod N. r b h ≡ m e ( mod N ) .
初始时 r = 1 r=1 r = 1 、b = m b=m b = m 、h = e h=e h = e ,故成立。若 h = 2 j h=2j h = 2 j ,更新把 b h b^h b h 变为 ( b 2 ) j (b^2)^j ( b 2 ) j ;若 h = 2 j + 1 h=2j+1 h = 2 j + 1 ,先把多出的一个 b b b 移到 r r r 中,再令 h h h 变为 j j j 。两种情况下不变量都保持。正整数反复减半最终为零,结束时 h = 0 h=0 h = 0 ,故 r ≡ m e ( m o d N ) r\equiv m^e\pmod N r ≡ m e ( mod N ) 。循环次数与 e e e 的二进制位数成正比;实际位复杂度还取决于整数乘法和约化算法及 N N N 的大小。
例如用 13 = 8 + 4 + 1 13=8+4+1 13 = 8 + 4 + 1 计算 7 13 m o d 55 7^{13}\bmod55 7 13 mod 55 :平方依次为 7 2 ≡ 49 7^2\equiv49 7 2 ≡ 49 、7 4 ≡ 36 7^4\equiv36 7 4 ≡ 36 、7 8 ≡ 31 7^8\equiv31 7 8 ≡ 31 ,结果是 31 ⋅ 36 ⋅ 7 ≡ 16 ⋅ 7 ≡ 2 ( m o d 55 ) 31\cdot36\cdot7\equiv16\cdot7\equiv2\pmod{55} 31 ⋅ 36 ⋅ 7 ≡ 16 ⋅ 7 ≡ 2 ( mod 55 ) 。不同的乘法次序给出相同的剩余类,而每步约化可避免整数不必要地增长。
当指数保密时,这种简单循环的分支依赖指数的位,运行时间或其他侧信道可能泄露信息。不变量证明数学结果,却不证明执行时间恒定。实现安全需要额外工程。
用欧几里得算法求逆
扩展欧几里得算法既检验指数是否有效,也给出逆元。对上面的密钥,
40 = 13 ⋅ 3 + 1 , 1 = 40 − 13 ⋅ 3. 40=13\cdot3+1,\qquad 1=40-13\cdot3. 40 = 13 ⋅ 3 + 1 , 1 = 40 − 13 ⋅ 3.
因此 − 13 -13 − 13 是 3 模 40 的逆元,其正代表是 27。一般而言,贝祖等式给出整数 s , t s,t s , t 使 s e + t φ = gcd ( e , φ ) se+t\varphi=\gcd(e,\varphi) se + tφ = g cd( e , φ ) 。若最大公因数为一,s s s 是逆元;若大于一,则逆元不可能存在:公因数会同时整除 e d ed e d 和 e d − 1 ed-1 e d − 1 ,从而整除 1,矛盾。
逆元的不同整数代表形如 d + j φ d+j\varphi d + j φ 。选正代表使解密的幂对所有剩余类都有定义,包括零;负次幂要求可逆,会排除非单位消息。添加 φ \varphi φ 的倍数不会改变逆元关系。
快速检查
(求 7 模 40 的逆元,并说明它如何由贝祖等式得出。)
解答 · 答案 由 40 = 5 ⋅ 7 + 5 40=5\cdot7+5 40 = 5 ⋅ 7 + 5 、7 = 1 ⋅ 5 + 2 7=1\cdot5+2 7 = 1 ⋅ 5 + 2 、5 = 2 ⋅ 2 + 1 5=2\cdot2+1 5 = 2 ⋅ 2 + 1 ,回代得 1 = 3 ⋅ 40 − 17 ⋅ 7 1=3\cdot40-17\cdot7 1 = 3 ⋅ 40 − 17 ⋅ 7 。故 − 17 ≡ 23 ( m o d 40 ) -17\equiv23\pmod{40} − 17 ≡ 23 ( mod 40 ) 是逆元;验算 7 ⋅ 23 = 161 ≡ 1 ( m o d 40 ) 7\cdot23=161\equiv1\pmod{40} 7 ⋅ 23 = 161 ≡ 1 ( mod 40 ) 。
快速检查
(模 55 用反复平方法算 2 10 2^{10} 2 10 。)
解答 · 答案 2 2 = 4 2^2=4 2 2 = 4 、2 4 = 16 2^4=16 2 4 = 16 、2 8 = 256 ≡ 36 2^8=256\equiv36 2 8 = 256 ≡ 36 。由 10 = 8 + 2 10=8+2 10 = 8 + 2 ,得 2 10 ≡ 36 ⋅ 4 = 144 ≡ 34 ( m o d 55 ) 2^{10}\equiv36\cdot4=144\equiv34\pmod{55} 2 10 ≡ 36 ⋅ 4 = 144 ≡ 34 ( mod 55 ) 。先后约化结果相同。
显式合并同余
正确性证明只用了唯一性,中国剩余定理还可由两个剩余类构造模 p q pq pq 的唯一解。因为 p , q p,q p , q 互素,存在整数 u , v u,v u , v 满足 u p + v q = 1 up+vq=1 u p + v q = 1 。给定模 p p p 的 a a a 和模 q q q 的 b b b ,令
x = a v q + b u p . x=avq+bup. x = a v q + b u p .
模 p p p 时 v q ≡ 1 vq\equiv1 v q ≡ 1 、u p ≡ 0 up\equiv0 u p ≡ 0 ,所以 x ≡ a x\equiv a x ≡ a ;模 q q q 时 u p ≡ 1 up\equiv1 u p ≡ 1 、v q ≡ 0 vq\equiv0 v q ≡ 0 ,所以 x ≡ b x\equiv b x ≡ b 。另一个解与 x x x 的差同时被两个素数整除,故被 p q pq pq 整除。此证明同时给出存在性和唯一性,不要求 a , b a,b a , b 可逆。
求模 55 下模 5 等于 2、模 11 等于 4 的剩余类。由 1 = 9 ⋅ 5 − 4 ⋅ 11 1=9\cdot5-4\cdot11 1 = 9 ⋅ 5 − 4 ⋅ 11 ,取 u = 9 , v = − 4 u=9,v=-4 u = 9 , v = − 4 。公式给出 x = 2 ( − 4 ) ( 11 ) + 4 ( 9 ) ( 5 ) = 92 ≡ 37 ( m o d 55 ) x=2(-4)(11)+4(9)(5)=92\equiv37\pmod{55} x = 2 ( − 4 ) ( 11 ) + 4 ( 9 ) ( 5 ) = 92 ≡ 37 ( mod 55 ) 。验算 37 ≡ 2 ( m o d 5 ) 37\equiv2\pmod5 37 ≡ 2 ( mod 5 ) 、37 ≡ 4 ( m o d 11 ) 37\equiv4\pmod{11} 37 ≡ 4 ( mod 11 ) 。直接把 2 与 4 相加并不能满足条件。
知道因子的人可以分别在两个素数模下计算幂,再重构模 N N N 的答案。实际私钥运算常利用这个方法加速,但实现也须处理故障并保护素因子;数学恒等式本身不提供这些防护。
概念视角 结构
由中国剩余定理粘合的两个幂映射 约化给出环同构 Z N → Z p × Z q \mathbb Z_N\to\mathbb Z_p\times\mathbb Z_q Z N → Z p × Z q ;在此同构下,m ↦ m e m\mapsto m^e m ↦ m e 变成 Z p \mathbb Z_p Z p 与 Z q \mathbb Z_q Z q 上各自的映射 x ↦ x e x\mapsto x^e x ↦ x e 。在 Z p \mathbb Z_p Z p 上零是不动点,每个非零 x x x 都满足 x p − 1 = 1 x^{p-1}=1 x p − 1 = 1 ,所以只要 e d ≡ 1 ( m o d p − 1 ) ed\equiv1\pmod{p-1} e d ≡ 1 ( mod p − 1 ) ,x ↦ x d x\mapsto x^d x ↦ x d 就能还原 x ↦ x e x\mapsto x^e x ↦ x e 。因此解密只需要 e d ≡ 1 ed\equiv1 e d ≡ 1 模 p − 1 p-1 p − 1 与模 q − 1 q-1 q − 1 成立,即模 lcm ( p − 1 , q − 1 ) \operatorname{lcm}(p-1,q-1) lcm ( p − 1 , q − 1 ) 成立。对 N = 55 N=55 N = 55 ,这个模数是 20 20 20 ,所以 d = 7 d=7 d = 7 已经是 e = 3 e=3 e = 3 的逆。
确定性会泄露什么?
假设观察者知道某个原始 RSA 明文只能是 2 或 3。观察者可用公钥分别对两个候选值求幂,再把结果与密文比较。对玩具公钥 ( 55 , 3 ) (55,3) ( 55 , 3 ) ,密文分别为 2 3 = 8 2^3=8 2 3 = 8 和 3 3 = 27 3^3=27 3 3 = 27 。看到 8 就能识别第一个候选值,观察者无需在此比较中先分解 55。例子虽小,比较的根源是确定性和可猜测的消息集合,不只是模数太小。
此映射还保持乘法:若 c 1 ≡ m 1 e c_1\equiv m_1^e c 1 ≡ m 1 e 、c 2 ≡ m 2 e c_2\equiv m_2^e c 2 ≡ m 2 e ,则 c 1 c 2 ≡ ( m 1 m 2 ) e ( m o d N ) c_1c_2\equiv(m_1m_2)^e\pmod N c 1 c 2 ≡ ( m 1 m 2 ) e ( mod N ) 。这是模乘法交换律的结果。修改密文可能使解密结果发生可预测的变化。例如模 55、指数 3 时,7 的密文是 13;将它乘以 2 3 = 8 2^3=8 2 3 = 8 得 104 ≡ 49 104\equiv49 104 ≡ 49 。修改后的密文正是 14 的原始加密,正确性保证其解密结果为 14。这一算术观察不是安全修改真实密文的方法;安全编码和协议需要考虑这种行为。
数字签名的目标不同于加密。真实性和保密性需要不同的安全定义,即使二者都可能涉及模幂。仅将教材公式的名称对调并不能定义安全签名方案。本节证明的是加解密恒等式,不证明任何签名协议的安全性或设计正确性。
快速检查
(用玩具公钥 ( 55 , 3 ) (55,3) ( 55 , 3 ) 分别加密候选消息 4 和 5。若已知消息是两者之一,能否从原始密文区分?)
解答 · 答案 两个密文模 55 分别是 4 3 = 64 ≡ 9 4^3=64\equiv9 4 3 = 64 ≡ 9 和 5 3 = 125 ≡ 15 5^3=125\equiv15 5 3 = 125 ≡ 15 。观察到的剩余类足以在两候选值中选择。推断使用了已知候选集合及确定性公钥加密,并不是恢复任意长消息的通用方法。
快速检查
(求 0 ≤ x < 55 0\le x<55 0 ≤ x < 55 且 x ≡ 1 ( m o d 5 ) x\equiv1\pmod5 x ≡ 1 ( mod 5 ) 、x ≡ 3 ( m o d 11 ) x\equiv3\pmod{11} x ≡ 3 ( mod 11 ) 的数。)
解答 · 答案 该范围内模 11 等于 3 的数是 3 , 14 , 25 , 36 , 47 3,14,25,36,47 3 , 14 , 25 , 36 , 47 ,只有 36 模 5 等于 1,所以 x = 36 x=36 x = 36 。定理保证模 55 唯一。枚举适用于这个小例子,但对大模数不是高效的一般方法。
数值例子把消息表示为零到 N − 1 N-1 N − 1 的整数。文本消息还需要明确规定如何编码到该范围以及如何还原。任意字节序列未必能装入一个剩余类,分块又带来新的设计问题。这些表示选择属于加密方案,而非费马定理的推论;声称程序能加密文本前必须先规定。上面的证明只说明已经选定一个剩余类后,两次模幂运算之间的关系。
比较证明与安全问题
在正确性证明中,公钥与私钥之间的同余关系是已知假设;结论是对每个合法消息,按照给定运算先加密后解密会得到原来的剩余类。它不考察攻击者能看到什么、能否请求其他加密或解密,也不衡量成功猜测消息的概率。安全定义必须先规定这些能力和成功事件,才能判断某方案抵抗什么攻击。即便模幂运算准确无误,确定性编码导致的候选比较仍然成立。
正确性也不意味着每一种参数都可用。若 p = q p=q p = q ,本节使用的两个不同素数的合并论证及 ( p − 1 ) ( q − 1 ) (p-1)(q-1) ( p − 1 ) ( q − 1 ) 形式不能直接照搬;若 e e e 与 φ \varphi φ 不互素,所需逆元不存在。列出假设不是形式上的装饰,它们对应密钥构造和证明中的具体步骤。