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 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). 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 ( m o d φ ( n ) ) ed\equiv1\pmod{\varphi(n)} e d ≡ 1 ( mod φ ( n )) k k k
e d = 1 + k ( p − 1 ) ( q − 1 ) ed=1+k(p-1)(q-1) e d = 1 + k ( p − 1 ) ( q − 1 ) と書くことができる。
p ∣ m p\mid m p ∣ m m ≡ 0 ( m o d p ) m\equiv0\pmod p m ≡ 0 ( mod p ) m e d ≡ 0 ≡ m ( m o d p ) m^{ed}\equiv0\equiv m\pmod p m e d ≡ 0 ≡ m ( mod p ) p ∤ m p\nmid m p ∤ m p p p 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\bigl(m^{p-1}\bigr)^{k(q-1)}\equiv m\pmod p m e d = m ( m p − 1 ) k ( q − 1 ) ≡ m ( mod p ) となる。よって、p ∣ m p\mid m p ∣ m p ∤ m p\nmid m p ∤ m m e d ≡ m ( m o d p ) m^{ed}\equiv m\pmod p m e d ≡ m ( mod p )
q ∣ m q\mid m q ∣ m m ≡ 0 ( m o d q ) m\equiv0\pmod q m ≡ 0 ( mod q ) m e d ≡ 0 ≡ m ( m o d q ) m^{ed}\equiv0\equiv m\pmod q m e d ≡ 0 ≡ m ( mod q ) q ∤ m q\nmid m q ∤ m q q q m q − 1 ≡ 1 ( m o d q ) m^{q-1}\equiv1\pmod q m q − 1 ≡ 1 ( mod q )
m e d = m ( m q − 1 ) k ( p − 1 ) ≡ m ( m o d q ) m^{ed}=m\bigl(m^{q-1}\bigr)^{k(p-1)}\equiv m\pmod q m e d = m ( m q − 1 ) k ( p − 1 ) ≡ m ( mod q ) となる。よって、q ∣ m q\mid m q ∣ m q ∤ m q\nmid m q ∤ m m e d ≡ m ( m o d q ) m^{ed}\equiv m\pmod q m e d ≡ m ( mod q )
p p p q q q p p p q q q
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 = 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
Miller の1976年の論文は、オイラー関数を計算する問題を含む一群の関数計算と整数の素因数分解との計算量上の関係を扱っています。秘密指数が得られた場合には、その情報から素因数分解を回収する議論があります。しかし、秘密指数を経由せず、公開鍵と暗号文から平文を直接回収する RSA 問題が素因数分解と同じ難しさをもつことは、この関係からは導かれません。
鍵長の要件は用途と求める安全性強度によって異なります。NIST SP 800-56B Rev. 2 は、NIST の整数因数分解型鍵確立方式において、少なくとも112ビットの安全性強度を与える偶数の法長として
2048ビット以上を要求しています。この数値をすべての用途に共通する標準鍵長とみなすことはできません。
十分な能力をもつ量子計算機では、ショアのアルゴリズムによって整数の素因数分解を多項式時間で行うことができるため、RSA は脆弱です。NIST は耐量子暗号標準への移行を案内していますが、将来の時点や移行の完了時期をここでは断定しません。
この記事が扱う対象は padding を付けない textbook RSA です。実際の暗号方式で必要になる padding、署名、通信規約、処理時間や消費電力から秘密情報が漏れる攻撃への対策は扱いません。したがって、復号の正しさの定理だけから実装の安全性を結論することはできません。
4 つまずいたら
e d ≡ 1 ed\equiv1 e d ≡ 1 φ ( n ) \varphi(n) φ ( n ) n n n 繰り返し二乗法の各段では、必ず法n n n p p p q q q