動機
從未見面的發送者和接收者仍可能希望保密通訊。公鑰加密把加密所需的資訊與解密所需的資訊分開。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 φ 不互質,所需逆元不存在。列出假設不是形式上的裝飾,它們對應密鑰構造和證明中的具體步驟。