☆HOME☆ ☆数学のいずみ☆

高校生のための暗号論入門

@Author MASASI.Sanae  @Version 1.04;2003.1.22

0.はじめに

 インターネットの普及に伴って,ネット上における情報の機密保持,改ざん防止の方法として公開鍵暗号方式が注目を集めている。公開鍵方式の中でも最も普及しているのがRSA暗号と呼ばれるものである。
 この理論には基本的でかつ魅力的な数学の整数に関する理論が用いられている。高校数学レベルでも理解できる数学をもとに,暗号論の魅力を少しでも知っていただきたいと思う。

1.素数

1_1 素数・合成数

 整数a(a≠1)が1とa以外に約数をもたないときaを素数という。また素数でない整数を合成数という。(素数一覧参照

(例)7,11は素数。 12=22・3は合成数。

1_2 素数判定アルゴリズム

 素数を完全に定義する式が存在することは証明されていないし,また存在しないともわかっていない。
 与えられた奇数 n が素数であるかどうかを厳密に判定することは, n の桁数が増えるとかなり難しい。そのため,厳密に素数であるか否かを判定するより,『確率的に素数である』ことを判定する方法がよく用いられる。代表的なものとしてRabin判定法(誤り確率1/4)がある。
 判定をクリアしたとき(ほぼ素数であろうと考えて間違いがないと判定されたとき)その数を疑似素数という。

1_3 素因数分解の困難性

 数値を素数の積で表すを素因数分解という。
 素因数分解は小さな素数から順に2, 3, 5, 7… と次々に割り算していけばよいが,このような方法では大きな数の場合計算量が指数関数的に増えて大変である。現在では大きな数の素因数分解のアルゴリズムとして,1974年にPollardによって発表されたp-1法や1980年代から提案された方法として2次ふるい法や数体ふるい法がある。特に大きな数に対しては数体ふるい法が最も高速であると言われている。

2.法

2_1 剰余定理

 任意の整数a,b(b≠0)に対し,a=bq+r (0≦r<|b|)となるようなq(商)とr(剰余)が一意に存在する。

2_2 法と合同

 整数nで整数a,bで割った余りが等しいとき,aとbとはnを法として合同といいa≡b(mod n)で表す。

(例)17÷5=3...2,32÷5=6...2  ∴17≡32(mod 5)

2_3 法に関する演算

  1. a≡b,c≡d (mod n) ⇒ a±c≡b±d,ac≡bd (mod n)
  2. ca≡cb (mod n) ⇒ a≡b (mod n/(c,n))  ((c,n)はcとnの最大公約数)

3.最大公約数・最小公倍数

3_1 最大公約数

 2つの整数a,bのそれぞれの公約数のうちで最大の整数をa,bの最大公約数といい,GCD(a,b)または(a,b)であらわす。

(例)(10,6)=2, (24,36)=12


2つの数の最大公約数を求めるスクリプト
整数A:  整数B:
  最大公約数:

3_2 互いに素

 2つの整数a,bが(a,b)=1の関係にあるとき,aとbは互いに素であるという。

(例)3,5は互いに素。 (4,6)=2より4,6は互いに素ではない。

3_3 ユークリッドの互除法

 b≠0 のとき,a を b で割った余りを r とおくと (a,b) = (b,r) が成り立つ。

 次のアルゴリズムにより最大公約数が求まる:

  1. a0= a,a1= b
  2. an=mod(an-2,an-1) (n=2, 3,…)
  3. an=0 となるとき (a,b)=an-1

(例)5916と1716の最大公約数12を求める。

i ai 計算
0 a0=5916  
1 a1=1716 5916÷1716=3...768
2 a2=768 1716÷768=2...180
3 a3=180 768÷180=4...48
4 a4=48 180÷48=3...36
5 a5=36 48÷36=1...12
6 a6=12 36÷12=0

3_4 最小公倍数

 2つの整数a,bのそれぞれの公倍数のうちで最小の整数をa,bの最小公倍数といい,LCM(a,b)であらわす。
 a,bの最小公倍数をL=LCM(a,b),最大公約数をG=GCD(a,b)とするときL=a*b/Gが成り立つ。

(例)a=12,b=20のとき,G=4。 ∴L=12*20/4=60

3_5 RSA暗号の基本定理

 異なる素数p,qに対してn=pq,L=LCM(p-1,q-1)とする。任意の正の整数xに対して
    xmL+1≡x (mod n)  (mは整数)

(注)多くの文献,Webサイトでオイラー関数φ(N)=φ(p×q)=φ(p)×φ(q)=(p-1)×(q-1)を用いて再出現する旨の記述があるが,これでは不十分であろうと思われる。

(例)

4.逆元

4_1 記数法

  1. 10進数で表された数値nの各桁の数字をd,dn-1,・・・,d2,d1,d0としたとき,
       n=d×10+dn-1×10n-1+・・・+d2×102+d1×101+d0
  2. r進数で表された数値nの各桁の数字をd,dn-1,・・・,d2,d1,d0としたとき,n=ddn-1・・・d2d1d0(r)と表し,
       n=d×r+dn-1×rn-1+・・・+d2×r2+d1×r1+d0
  3. 10進数からr進数への変換は,rでわった時の余りがそれぞれの桁の係数となる。
       ddn-1・・・d2d1d0(r)=d×r+dn-1×rn-1+・・・+d2×r2+d1×r1+d0=(d×rn-1+dn-1×rn-2+・・・+d2×r1+d1)×r+d0

(例)

4_2 繰り返し2乗法

 nを法とするaeを効率よく計算する方法。

(例)32530(mod 23)の計算。

  1. 30を2進数表示   30=11110(2)
  2. 3252,3254,3258,32516を計算
    3252 =105625 ≡9  
    3254 ≡92 =81 ≡12
    3258 ≡122 =144 ≡6
    32516 ≡62 =36 ≡13
  3. 32530を計算
    32530 =32516×3258×3254×3252
    ≡13×6×12×9
    =78×108
    ≡9×16
    =144
    ≡6

ae mod n を求めるスクリプト
整数a:  整数e:  整数n:
  計算結果:

4_3 乗法逆元

 ax≡1(mod n)となるxをaの乗法に関する逆元という。 (a,n)=1のときnを法とするaの逆元が必ず存在する。

(例)

4_4 拡張ユークリッドの互除法

 aとb が互いに素ならばax+by=1を満たす整数x,yが次のアルゴリズムによって求まる。

  1. a0=a,a1=b
    x0= 1,x1=0
    y0= 0,y1=1
  2. q=an-1をanで割った商
    an = an-2-qn-1*an-1 (=an-2をrn-1で割った余り)
    xn = xn-2-qn-1*xn-1
    yn = yn-2-qn-1*yn-1 (n=2,3,…)
  3. an=0 となるnで
    an-1>0 のとき (a,b)=an-1,x=xn-1,y=yn-1
    an-1<0 のとき (a,b)=-an-1,x=-xn-1,y=-yn-1

4_5 逆元の存在

 整数aが法nと互いに素であるとき,ax≡1(mod n) を満たす整数xが拡張ユークリッドの互除法によって求まる。
 ax+ny=(a,n)=1を満たす整数x,yが求まるが,このときax=1-ny≡1 (mod n)より明らか。

(例)2184を法としたときの1241の逆元を求める。

i ai qi xi 計算
0 a0=1241   x0=1  
1 a1=2184 q1=0 x1=0 1241÷2184=0...2141
2 a2=1241 q2=1 x2=x0-q1・x1=1 2184÷1241=1...943
3 a3=943 q3=1 x3=x1-q2・x2=-1 1241÷943=1...298
4 a4=298 q4=3 x4=x2-q3・x3=2 943÷298=3...49
5 a5=49 q5=6 x5=x3-q4・x4=-7 298÷49=6...4
6 a6=4 q6=12 x6=x4-q3・x3=44 49÷4=12...1
7 a7=1 q7=4 x7=x5-q4・x4=-535 4÷1=4...0

 ∴ 2184-535=1649が1241の逆元。  (1241×1649=2046409≡1(mod 2184) より確かめられる。)


nを法とするeの逆元を求めるスクリプト
逆元を求める数e:  法とする数n:
  逆元:

5.暗号

5_1 暗号の定義

 元のデータを送信者と受信者以外の人には解読不可能なデータに変換する,または元に戻すための技法。

(例)

平文 暗号化 暗号文 複合化 平文
"apple" "dssoh" "apple"

5_2 暗号方式と鍵

 平文をアルファベット順にxづつずらして暗号文を作成するとする。このときの「アルファベット順にずらす」を暗号方式(アルゴリズム),「x」を鍵という。

(例1)

(例2)

5_3 暗号方式

  1. 共通鍵暗号方式
    あらかじめ送信者と受信者だけが取り決めて,互いに第三者に知らせないで運用する方式。ひとつの鍵で送信者が暗号化し,受信者は同じ鍵を使って複号化する。この方式で最も有名なものはDES (Data Encription Standard) と呼ばれる暗号方式で,1977年に規格化されている。56 ビットが一般的で,米国の銀行など世界で使われている。またIDEAは128ビットの鍵を使用する暗号で1990年に公開された。暗号化プログラムPGPで使われている。
  2. 公開鍵暗号方式
    2つの鍵が使われる。一方の鍵で閉じたら,その鍵では開けることができない。開くときには別の鍵が必要となる。片方を「秘密鍵」(自分だけが持っている鍵),もう一方を「公開鍵」(誰でも使えるところに公開する鍵)という。閉じる鍵と開く鍵が違うこと,片方が公開されているということから,従来の鍵に比べてとても柔軟に使え,かつ安全な暗号化を行うことができる。この方式の最も有名なものはRSA(Rivest, Shamir, Adlemanの3人の発明者の頭文字をとったもの) である。暗号化は「素因数分解」の困難性をもとに作られている。
  3. 共通鍵と公開鍵の併用

(例:共通鍵暗号方式)

"apple"をアルファベット順に3つずつずらして"dssoh"に暗号化。このときの「アルファベット順にずらす」が暗号化の規則(アルゴリズム)で,「3」が鍵となる。受信者以外に鍵を知られないことで秘匿性が守られる。

(例:公開鍵暗号化方式)

B氏の「公開鍵」で暗号化された情報はB氏の「秘密鍵」でしか復号化できない。逆にB氏の「秘密鍵」で暗号化された情報はB氏の「公開鍵」でしか復号化できない。

6.メッセージの数値化

6_1 メッセージの数値化

 現代暗号では文字を事前に決められた複数の文字ずつを単位として,いったん数値に変換した上で暗号化する。

(例)

6_2 ASCIIコード

 ASCIIコードでは0から127までの数値に次の表のような文字と数値を対応させる。

上位3ビット 0 1 2 3 4 5 6 7
下位3ビット
0 NUL DLE SP 0 @ P ` p
1 SOH DC1 ! 1 A Q a q
2 STX DC2 " 2 B R b r
3 ETX DC3 # 3 C S c s
4 EOT DC4 $ 4 D T d t
5 ENQ NAC % 5 E U e u
6 ACK SYN & 6 F V f v
7 BEL ETB ' 7 G W g w
8 BS CAN ( 8 H X h x
9 HT EM ) 9 I Y i y
A LF/NL SUB * : J Z j z
B VT ESC + ; K [ k {
C FF FS , < L \ l |
D CR GS - = M ] m }
E SO RS . > N ^ n ~
F SI US / ? O _ o DEL

6_3 暗号化ソフト

 米国のPhilip Zimmermann氏が開発した暗号ソフト「PGP(Pretty Good Privacy)」が有名。

7.RSA暗号

7_1 RSA暗号の概要
 平文をM,暗号文をCとすると,M<nのとき
   C≡Me (mod n)   (暗号化)
   M≡Cd (mod n)   (複合化)
 ここでe,nが公開鍵,dが秘密の鍵になる。

(例:暗号化) M=21をn=437,e=17で暗号化する。C=2117を最小2乗法を用いて計算。

  1. 17を2進数表示  17=10001(2)
  2. 212,214,218,2116を計算
    212 =441 ≡4  
    214 ≡42 =16  
    218 ≡162 =256  
    2116 ≡2562 =65536 ≡423
  3. 2117を計算
    2117 =2116×21
    ≡423×21
    =8883
    ≡143
    ∴ C=2117≡143 (mod 437)

(例:複合化) d=35で複合化する。上と同様に最小2乗法を用いて計算。

M'=14335≡21 (mod 437) 

7_2 鍵の作成の仕方@ 公開鍵nとe

  1. 2つの素数p,qを選ぶ(これは秘密の鍵となる)。
  2. p,qを元にn=pqとL=LCM(p-1,q-1)を計算する。
  3. Lと素な整数eを選択する。

(例)

  1. p=19,q=23
  2. n=19*23=437,L=LCM(19-1,23-1)=198
  3. e=17   (これは(17,198)=1より確かめられる)

7_3 鍵の作成の仕方A 秘密鍵d

Lを法とするeの逆元を計算する。

(例)L=198を法とするe=17の逆元dを拡張ユークリッドの互除法で計算する。

i ai qi xi 計算
0 a0=17   x0=1  
1 a1=198 q1=0 x1=0 17÷198=0...17
2 a2=17 q2=11 x2=x0-q1・x1=1 198÷17=11...11
3 a3=11 q3=1 x3=x1-q2・x2=-11 17÷11=1...6
4 a4=6 q4=1 x4=x2-q3・x3=12 11÷6=1...5
5 a5=5 q5=1 x5=x3-q4・x4=-23 6÷5=1...1
6 a6=1 q6=1 x5=x3-q4・x4=35 5÷1=5...0

7_4 RSA暗号の安全性

 素因数分解の困難性に基づく。まだ誰もその破り方を発見していない。

≪参考資料≫

☆HOME☆ ☆数学のいずみ☆