1 繰り返し二乗法 a r m o d m a^r\bmod m a r mod m r r r
定義 1.1 (繰り返し二乗法). a a a m m m 2 2 2 r r r 繰り返し二乗法 (repeated squaring )r = 0 r=0 r = 0 a 0 ≡ 1 ( m o d m ) a^0\equiv1\pmod m a 0 ≡ 1 ( mod m ) r ≥ 1 r\geq1 r ≥ 1 r r r
r = ∑ i = 0 s ε i 2 i , ε i ∈ { 0 , 1 } , ε s = 1 r=\sum_{i=0}^{s}\varepsilon_i2^i,
\qquad \varepsilon_i\in\{0,1\},\quad \varepsilon_s=1 r = i = 0 ∑ s ε i 2 i , ε i ∈ { 0 , 1 } , ε s = 1 と二進展開する。b 0 b_0 b 0 a a a m m m
b i ≡ b i − 1 2 ( m o d m ) ( 1 ≤ i ≤ s ) b_i\equiv b_{i-1}^2\pmod m\qquad(1\leq i\leq s) b i ≡ b i − 1 2 ( mod m ) ( 1 ≤ i ≤ s ) によって各b i b_i b i m m m b i ≡ a 2 i ( m o d m ) b_i\equiv a^{2^i}\pmod m b i ≡ a 2 i ( mod m ) ε i = 1 \varepsilon_i=1 ε i = 1 i i i b i b_i b i m m m
∏ ε i = 1 b i ≡ a r ( m o d m ) \prod_{\varepsilon_i=1}b_i\equiv a^r\pmod m ε i = 1 ∏ b i ≡ a r ( mod m ) である。二乗はs = ⌊ log 2 r ⌋ s=\lfloor\log_2r\rfloor s = ⌊ log 2 r ⌋ s s s r ≥ 1 r\geq1 r ≥ 1 O ( log r ) O(\log r) O ( log r ) O ( log r ) O(\log r) O ( log r )
例 1.2. 3 22 m o d 23 3^{22}\bmod23 3 22 mod 23 22 = 10110 2 = 16 + 4 + 2 22=10110_2=16+4+2 22 = 1011 0 2 = 16 + 4 + 2 23 23 23
3 1 ≡ 3 , 3 2 ≡ 9 , 3 4 ≡ 9 2 = 81 ≡ 12 , 3 8 ≡ 12 2 = 144 ≡ 6 , 3 16 ≡ 6 2 = 36 ≡ 13 ( m o d 23 ) 3^1\equiv3,\quad
3^2\equiv9,\quad
3^4\equiv9^2=81\equiv12,\quad
3^8\equiv12^2=144\equiv6,\quad
3^{16}\equiv6^2=36\equiv13\pmod{23} 3 1 ≡ 3 , 3 2 ≡ 9 , 3 4 ≡ 9 2 = 81 ≡ 12 , 3 8 ≡ 1 2 2 = 144 ≡ 6 , 3 16 ≡ 6 2 = 36 ≡ 13 ( mod 23 ) となる。したがって
3 22 ≡ 3 16 3 4 3 2 ≡ 13 ⋅ 12 ⋅ 9 ( m o d 23 ) . 3^{22}\equiv3^{16}3^4 3^2\equiv13\cdot12\cdot9\pmod{23}. 3 22 ≡ 3 16 3 4 3 2 ≡ 13 ⋅ 12 ⋅ 9 ( mod 23 ) . ここで
13 ⋅ 12 = 156 ≡ 18 ( m o d 23 ) , 18 ⋅ 9 = 162 ≡ 1 ( m o d 23 ) 13\cdot12=156\equiv18\pmod{23},
\qquad
18\cdot9=162\equiv1\pmod{23} 13 ⋅ 12 = 156 ≡ 18 ( mod 23 ) , 18 ⋅ 9 = 162 ≡ 1 ( mod 23 ) であるから、3 22 ≡ 1 ( m o d 23 ) 3^{22}\equiv1\pmod{23} 3 22 ≡ 1 ( mod 23 ) 23 23 23 23 ∤ 3 23\nmid3 23 ∤ 3 22 = 23 − 1 22=23-1 22 = 23 − 1
2 RSA 暗号 定義 2.1 (Textbook RSA). 次の鍵生成・暗号化・復号の方式をTextbook RSA (textbook RSA )p , q p,q p , q
n = p q , φ ( n ) = ( p − 1 ) ( q − 1 ) n=pq,\qquad \varphi(n)=(p-1)(q-1) n = pq , φ ( n ) = ( p − 1 ) ( q − 1 ) とする。1 < e < φ ( n ) 1<e<\varphi(n) 1 < e < φ ( n ) gcd ( e , φ ( n ) ) = 1 \gcd(e,\varphi(n))=1 g cd( e , φ ( n )) = 1 e e e
e d + k φ ( n ) = 1 ed+k\varphi(n)=1 e d + k φ ( n ) = 1 を満たす整数d , k d,k d , k d d d φ ( n ) \varphi(n) φ ( n ) 0 < d < φ ( n ) 0<d<\varphi(n) 0 < d < φ ( n ) ( n , e ) (n,e) ( n , e ) d d d
0 ≤ m < n 0\leq m<n 0 ≤ m < n m m m m e m^e m e n n n 0 ≤ c < n 0\leq c<n 0 ≤ c < n c c c c d c^d c d n n n 0 0 0 n n n
暗号化と復号のべき乗は、定義 1.1 によって計算することができます。次の定理では、この二つの操作が数学的に逆になることが示されます。
定理 2.2. p , q p,q p , q n = p q n=pq n = pq φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n)=(p-1)(q-1) φ ( n ) = ( p − 1 ) ( q − 1 ) 1 < e < φ ( n ) 1<e<\varphi(n) 1 < e < φ ( n ) gcd ( e , φ ( n ) ) = 1 \gcd(e,\varphi(n))=1 g cd( e , φ ( n )) = 1 e e e 0 < d < φ ( n ) 0<d<\varphi(n) 0 < d < φ ( n ) e d ≡ 1 ( m o d φ ( n ) ) ed\equiv1\pmod{\varphi(n)} e d ≡ 1 ( mod φ ( n )) d d d m m m 0 ≤ m < n 0\leq m<n 0 ≤ m < n
m e d ≡ m ( m o d n ) m^{ed}\equiv m\pmod n m e d ≡ m ( mod n ) である。
証明. e d − 1 ed-1 e d − 1 ( p − 1 ) ( q − 1 ) (p-1)(q-1) ( p − 1 ) ( q − 1 ) r ∈ { p , q } r\in\{p,q\} r ∈ { p , q } h h h e d = 1 + h ( r − 1 ) ed=1+h(r-1) e d = 1 + h ( r − 1 ) r ∣ m r\mid m r ∣ m e d ≥ 1 ed\ge1 e d ≥ 1 m e d ≡ 0 ≡ m ( m o d r ) m^{ed}\equiv0\equiv m\pmod r m e d ≡ 0 ≡ m ( mod r ) r ∤ m r\nmid m r ∤ m §A4.7 定理 1.1 により
m e d = m ( m r − 1 ) h ≡ m ( m o d r ) m^{ed}=m\bigl(m^{r-1}\bigr)^h\equiv m\pmod r m e d = m ( m r − 1 ) h ≡ m ( mod r ) である。したがって、m e d ≡ m ( m o d p ) m^{ed}\equiv m\pmod p m e d ≡ m ( mod p ) m e d ≡ m ( m o d q ) m^{ed}\equiv m\pmod q m e d ≡ m ( mod q ) p , q p,q p , q §A4.6 補題 2.1 の一意性によりm e d ≡ m ( m o d p q ) m^{ed}\equiv m\pmod{pq} m e d ≡ m ( mod pq ) n = p q n=pq n = pq ▨
命題 2.3. p , q p,q p , q n = p q n=pq n = pq t ≥ 1 t\ge1 t ≥ 1 m m m
m t ≡ m ( m o d n ) m^t\equiv m\pmod n m t ≡ m ( mod n ) が成り立つための必要十分条件は
lcm ( p − 1 , q − 1 ) ∣ ( t − 1 ) \operatorname{lcm}(p-1,q-1)\mid(t-1) lcm ( p − 1 , q − 1 ) ∣ ( t − 1 ) である。
証明. t = 1 t=1 t = 1 m t = m m^t=m m t = m t − 1 = 0 t-1=0 t − 1 = 0 t ≥ 2 t\ge2 t ≥ 2
すべての整数m m m m t ≡ m ( m o d n ) m^t\equiv m\pmod n m t ≡ m ( mod n ) r ∈ { p , q } r\in\{p,q\} r ∈ { p , q } §A4.12 定理 3.2 により、法r r r g g g m = g m=g m = g g t ≡ g ( m o d r ) g^t\equiv g\pmod r g t ≡ g ( mod r ) gcd ( g , r ) = 1 \gcd(g,r)=1 g cd( g , r ) = 1 §A4.3 補題 1.1 によりu g + v r = 1 ug+vr=1 ug + v r = 1 u , v u,v u , v u u u g t − 1 ≡ 1 ( m o d r ) g^{t-1}\equiv1\pmod r g t − 1 ≡ 1 ( mod r ) g g g φ ( r ) = r − 1 \varphi(r)=r-1 φ ( r ) = r − 1 §A4.12 命題 1.2 を正整数t − 1 t-1 t − 1 r − 1 ∣ t − 1 r-1\mid t-1 r − 1 ∣ t − 1 p − 1 p-1 p − 1 q − 1 q-1 q − 1 t − 1 t-1 t − 1 t − 1 t-1 t − 1
逆に、lcm ( p − 1 , q − 1 ) ∣ ( t − 1 ) \operatorname{lcm}(p-1,q-1)\mid(t-1) lcm ( p − 1 , q − 1 ) ∣ ( t − 1 ) m m m r ∈ { p , q } r\in\{p,q\} r ∈ { p , q } h h h t = 1 + h ( r − 1 ) t=1+h(r-1) t = 1 + h ( r − 1 ) r ∣ m r\mid m r ∣ m m t ≡ 0 ≡ m ( m o d r ) m^t\equiv0\equiv m\pmod r m t ≡ 0 ≡ m ( mod r ) r ∤ m r\nmid m r ∤ m §A4.7 定理 1.1 により
m t = m ( m r − 1 ) h ≡ m ( m o d r ) m^t=m\bigl(m^{r-1}\bigr)^h\equiv m\pmod r m t = m ( m r − 1 ) h ≡ m ( mod r ) である。よって、m t ≡ m ( m o d p ) m^t\equiv m\pmod p m t ≡ m ( mod p ) m t ≡ m ( m o d q ) m^t\equiv m\pmod q m t ≡ m ( mod q ) p , q p,q p , q §A4.6 補題 2.1 の一意性によりm t ≡ m ( m o d n ) m^t\equiv m\pmod n m t ≡ m ( mod n ) ▨
例 2.4. p = 5 p=5 p = 5 q = 11 q=11 q = 11 n = 55 n=55 n = 55 φ ( n ) = 40 \varphi(n)=40 φ ( n ) = 40 lcm ( p − 1 , q − 1 ) = 20 \operatorname{lcm}(p-1,q-1)=20 lcm ( p − 1 , q − 1 ) = 20 e = 3 e=3 e = 3 d = 7 d=7 d = 7
e d = 21 ≡ 1 ( m o d 20 ) , e d ≢ 1 ( m o d 40 ) ed=21\equiv1\pmod{20},\qquad ed\not\equiv1\pmod{40} e d = 21 ≡ 1 ( mod 20 ) , e d ≡ 1 ( mod 40 ) である。命題 2.3 をt = e d t=ed t = e d 0 ≤ m < 55 0\le m<55 0 ≤ m < 55 m m m m ↦ m 3 m\mapsto m^3 m ↦ m 3 7 7 7 e d ≡ 1 ( m o d φ ( n ) ) ed\equiv1\pmod{\varphi(n)} e d ≡ 1 ( mod φ ( n ))
例 2.5. p = 3 p=3 p = 3 q = 11 q=11 q = 11
n = 33 , φ ( n ) = ( 3 − 1 ) ( 11 − 1 ) = 20 n=33,\qquad\varphi(n)=(3-1)(11-1)=20 n = 33 , φ ( n ) = ( 3 − 1 ) ( 11 − 1 ) = 20 である。e = 3 e=3 e = 3 1 < 3 < 20 1<3<20 1 < 3 < 20 gcd ( 3 , 20 ) = 1 \gcd(3,20)=1 g cd( 3 , 20 ) = 1
20 = 6 ⋅ 3 + 2 , 3 = 1 ⋅ 2 + 1 , 20=6\cdot3+2,\qquad3=1\cdot2+1, 20 = 6 ⋅ 3 + 2 , 3 = 1 ⋅ 2 + 1 , 1 = 3 − 2 = 3 − ( 20 − 6 ⋅ 3 ) = 7 ⋅ 3 − 20 1=3-2=3-(20-6\cdot3)=7\cdot3-20 1 = 3 − 2 = 3 − ( 20 − 6 ⋅ 3 ) = 7 ⋅ 3 − 20 である。したがって3 ⋅ 7 + ( − 1 ) ⋅ 20 = 1 3\cdot7+(-1)\cdot20=1 3 ⋅ 7 + ( − 1 ) ⋅ 20 = 1 20 20 20 d = 7 d=7 d = 7
平文m = 4 m=4 m = 4
c ≡ 4 3 = 64 ≡ 31 ( m o d 33 ) c\equiv4^3=64\equiv31\pmod{33} c ≡ 4 3 = 64 ≡ 31 ( mod 33 ) である。暗号文の代表はc = 31 c=31 c = 31 7 = 4 + 2 + 1 7=4+2+1 7 = 4 + 2 + 1 33 33 33 31 ≡ − 2 ( m o d 33 ) 31\equiv-2\pmod{33} 31 ≡ − 2 ( mod 33 )
31 2 ≡ 4 , 31 4 ≡ 4 2 = 16 ( m o d 33 ) 31^2\equiv4,\qquad31^4\equiv4^2=16\pmod{33} 3 1 2 ≡ 4 , 3 1 4 ≡ 4 2 = 16 ( mod 33 ) となる。さらに
31 7 ≡ 31 4 ⋅ 31 2 ⋅ 31 ≡ 16 ⋅ 4 ⋅ 31 ≡ 31 ⋅ 31 ≡ ( − 2 ) 2 ≡ 4 ( m o d 33 ) . 31^7\equiv31^4\cdot31^2\cdot31
\equiv16\cdot4\cdot31
\equiv31\cdot31
\equiv(-2)^2
\equiv4\pmod{33}. 3 1 7 ≡ 3 1 4 ⋅ 3 1 2 ⋅ 31 ≡ 16 ⋅ 4 ⋅ 31 ≡ 31 ⋅ 31 ≡ ( − 2 ) 2 ≡ 4 ( mod 33 ) . 復号で得た4 4 4 m = 4 m=4 m = 4
3 数学的な正しさと安全性の前提 定理 2.2 では、鍵が定められた後の復号が正しいことが証明されています。この定理では、公開情報から秘密指数を求める計算が難しいことは主張されていません。
素因数p , q p,q p , q φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n)=(p-1)(q-1) φ ( n ) = ( p − 1 ) ( q − 1 ) d d d n = p q n=pq n = pq p , q p,q p , q
問題 3.1. n = p q n=pq n = pq n n n φ ( n ) \varphi(n) φ ( n ) p , q p,q p , q n = 3233 n=3233 n = 3233 φ ( n ) = 3120 \varphi(n)=3120 φ ( n ) = 3120
解答. φ ( n ) = ( p − 1 ) ( q − 1 ) = n − ( p + q ) + 1 \varphi(n)=(p-1)(q-1)=n-(p+q)+1 φ ( n ) = ( p − 1 ) ( q − 1 ) = n − ( p + q ) + 1
S = n + 1 − φ ( n ) S=n+1-\varphi(n) S = n + 1 − φ ( n ) とおけばS = p + q S=p+q S = p + q p , q p,q p , q
T 2 − S T + n = 0 T^2-ST+n=0 T 2 − S T + n = 0 の二つの解である。判別式は
S 2 − 4 n = ( p + q ) 2 − 4 p q = ( p − q ) 2 S^2-4n=(p+q)^2-4pq=(p-q)^2 S 2 − 4 n = ( p + q ) 2 − 4 pq = ( p − q ) 2 であり、p ≠ q p\ne q p = q p , q p,q p , q
S − S 2 − 4 n 2 , S + S 2 − 4 n 2 \frac{S-\sqrt{S^2-4n}}2,\qquad\frac{S+\sqrt{S^2-4n}}2 2 S − S 2 − 4 n , 2 S + S 2 − 4 n によって求まる。両式の分子はp + q − ∣ p − q ∣ p+q-|p-q| p + q − ∣ p − q ∣ p + q + ∣ p − q ∣ p+q+|p-q| p + q + ∣ p − q ∣ p , q p,q p , q φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n)=(p-1)(q-1) φ ( n ) = ( p − 1 ) ( q − 1 )
与えられた値ではS = 3233 + 1 − 3120 = 114 S=3233+1-3120=114 S = 3233 + 1 − 3120 = 114
S 2 − 4 n = 114 2 − 4 ⋅ 3233 = 64 S^2-4n=114^2-4\cdot3233=64 S 2 − 4 n = 11 4 2 − 4 ⋅ 3233 = 64 である。したがって、二つの素因数は
114 − 8 2 = 53 , 114 + 8 2 = 61 \frac{114-8}{2}=53,\qquad\frac{114+8}{2}=61 2 114 − 8 = 53 , 2 114 + 8 = 61 である。実際に53 ⋅ 61 = 3233 53\cdot61=3233 53 ⋅ 61 = 3233 ( 53 − 1 ) ( 61 − 1 ) = 3120 (53-1)(61-1)=3120 ( 53 − 1 ) ( 61 − 1 ) = 3120 ▨
Miller の1976年の論文は、オイラー関数を計算する問題を含む一群の関数計算と整数の素因数分解との計算量上の関係を扱っています。論文の序論で述べられる同値性には、拡張リーマン予想の仮定が付いています。秘密指数が得られた場合には、その情報から素因数分解を回収する議論があります。しかし、秘密指数を経由せず、公開鍵と暗号文から平文を直接回収する RSA 問題が素因数分解と同じ難しさをもつことは、この関係からは導かれません。
鍵長の要件は用途と求める安全性強度によって異なります。NIST SP 800-56B Rev. 2 は、NIST の整数因数分解型鍵確立方式において、少なくとも112ビットの安全性強度を与える偶数の法長として
2048ビット以上を要求しています。この数値をすべての用途に共通する標準鍵長とみなすことはできません。
十分な能力をもつ量子計算機では、ショアのアルゴリズムによって整数の素因数分解を多項式時間で行うことができるため、RSA は脆弱です。NIST は耐量子暗号標準への移行を案内していますが、将来の時点や移行の完了時期を、素因数分解のアルゴリズムの存在だけから決めることはできません。
この記事で扱う対象は padding を付けない textbook RSA です。実際の暗号方式で必要になる padding、署名、通信規約、処理時間や消費電力から秘密情報が漏れる攻撃への対策は扱いません。したがって、復号の正しさの定理だけから実装の安全性を結論することはできません。