馬場良始 90 平文 : book 暗号文 : errn となる. 単純に文字をずらすシーザー暗号は改良され, 文字の置き換え表を作り, それに従って暗号化復号をする換字式暗号が作られた. しかし, ある文字を単に別の文字に置き換えるような換字式暗号は, 頻度分析により簡単に解読される.

Size: px

Start display at page:

Download "馬場良始 90 平文 : book 暗号文 : errn となる. 単純に文字をずらすシーザー暗号は改良され, 文字の置き換え表を作り, それに従って暗号化復号をする換字式暗号が作られた. しかし, ある文字を単に別の文字に置き換えるような換字式暗号は, 頻度分析により簡単に解読される."

いとはやたけ
7 years ago
Views:

1 , RSA, 17,. (,,.),,.,,, RSA, RSA, RSA.,,, RSA I. 1.,, (,,, 3 ),., IC ( IC ),.,.,,.,.,. ( ) :. :. :,. (, ( ) ) :,. :,. (,, 3.) II.. (,.),.,., (, ),., 3

2 馬場良始 90 平文 : book 暗号文 : errn となる. 単純に文字をずらすシーザー暗号は改良され, 文字の置き換え表を作り, それに従って暗号化復号をする換字式暗号が作られた. しかし, ある文字を単に別の文字に置き換えるような換字式暗号は, 頻度分析により簡単に解読される. たとえば英語だと e や t といった文字の使用頻度が高い the という単語がよく使われる, tion のような綴りのパターンが多用されるなどの, 元の言語が持っている特徴が暗号文の中に残ってしまうので, それを手がかりにして解読されてしまう *1. 頻度分析法が発達し, 単なる換字式暗号の安全性が低下したので, 16 世紀頃, 言語の特徴を暗号文に (ほとんど) 出さない新たな換字式暗号であるヴィジュネル暗号が考案された (詳細は, 例えば [27] 参照). この暗号は非常に安全性が高く解読不能の暗号とも呼ばれたが, 1863 年に暗号文から言語の特徴を見いだす方法が見つけ出され破られてしまった. この間, 18 世紀には, ヨーロッパの列強各国が, 他国の通信文の入手解読を行うブラックチェンバーと呼ばれる国家秘密情報機関を作るようになったり, 19 世紀中頃には, 電信が実用化されて, 通信文は傍受解読されるものとして, 暗号を用いるのが常識となったりした結果, 安全な暗号の必要性はさらに高まった. さらに 19 世紀末には無線が発明され, 電線を引くことなく地球上のどことでも通信が可能 (傍受も可能) になった. ほぼ同時期に第 1 次世界大戦が勃発し, 安心して無線で通信できる強力な暗号の開発が急務となったが, 生み出された暗号は, 短期間の間に解読されるか, 実用性がないかのいずれかであった. 第 1 次世界大戦後, 容易に破られない暗号解読技術を求めて, さらに複雑な手順の暗号が次々に考案された. そして, そのような複雑な手順を簡単な操作で間違いなく行うために, 機械式の暗号機が作られるようになった. このようなものの中で, 歴史上特に有名なものに, 第 2 次世界大戦中にドイツ軍が使用していたエニグマ暗号機がある. 解読されない強い暗号を求めて, さまざまな暗号システムが考え出された中で, 換字のしくみをもっと複雑にし, さらに１文字ごとに暗号化手順を変えるという, 当時おそらく最強の暗号システムであり, しかも鍵は毎日変更された. 暗号機は持ち運び可能なタイプライター型で, 1 兆を越す暗号鍵を簡単に設定選択でき, 暗号文の復号も同じ暗号機でできた. 第１次世界大戦の結果, 再び独立国となったポーランドは, 国家維持のために隣国であるドイツ, ロシアの通信暗号エニグマ暗号機を解読し続ける必要に迫られていた. 暗号解読は, 国家の ( [21] から引用 ) 存続を賭けた最重要課題であったのだ. そして, 1930 年代に, ドイツ軍が絶対の自信を持っていたエニグマは, ポーランド暗号局に所属していた数学者マリアンレイェフスキによった破られるこ *1 このような解読手法は, エジプトのヒエログリフ, バビロニアの楔形文字, 古代トルコのルーネ文字, インドのブラーフミー文字などの古代文字解読にも使われた.

頻度分析法が発達し, 単なる換字式暗号の安全性が低下したので, 16 世紀頃, 言語の特徴を暗号文に (ほとんど) 出さない新たな換字式暗号であるヴィジュネル暗号が考案された (詳細は, 例えば [27] 参照). この暗号は非常に安全性が高く解読不能の暗号とも呼ばれたが, 1863 年に暗号文から言語の特徴を見いだす方法が見つけ出され破られてしまった.

3 91 * ,,., ,.,,.,,, *3., ,, 2., U,.,,, (, 7 ), (. ), ( ).,,,., 2,,. 1.,, 3 /. 2,,., *4.,, 1974., 2, *5., 2,., 3 (,, ),,, ,.,,, *6 *7., *2,,, ,,. *3,. *4,., 3., DES, (NSA), PGP 1990, RSA,,,,.,,., 1974.,. *5,,.,,. *6. *7.,

, 2, *5., 2,., 3 (,, ),,, 1935 2,.,,, *6 *7., *2,,, 3. 3 1,,.

4 92 The Ten Pointed-Note ( ), *8., *9,,, (, ),., * ,., (,,,, ).,,.,,., (, [27, V ] ) 2,,. 3. 1,.,,, 1936 On Computable.,.,,,,,.,,,,. *8,, Gerald Nye (Nye Committee, ),,,, ( ),., 2,, 2, 3, 2., 2., ( ), 1933.,., 2,,. *9,.,,, 2008, 710, 109, 69, 218, 364, 68, 69, 8 19,. (2,.), 1,, 12 15, 3, 1., 8,.,. 1.,.,,,,. *10,.

.,,,,. *8,, Gerald Nye (Nye Committee, 1934 4 ),,,, ( ),., 2,, 2, 3, 2., 2., ( ), 1933.

5 93 Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc. (1936), *11.,,, ( ),, ( ).,,., ( ), *12.,,,,,,.,., (. 2 ), EDVAC (Electronic Discrete Variable Calculator) ( EDVAC ),, 1945., EDVAC., EDVAC,, 1949 *13 EDSAC (Electronic Delay Storage Automatic Calculator) * ,., 1959 IC, 1960,.,,,.,,., 1977 (NBS), IBM DES (Data Encryption Standard) ( ) *11 (Entscheidungsproblem),. ( )?,.,., ( ),,,.,,. ( ,,.,,,.,,.) *12, (,. ). *13, 1946, EDVAC. *14, EDSAC , Baby Mark I., (, ),, Mark I,.

13.,., 1959 IC, 1960,.,,,.,,., 1977 (NBS), IBM DES (Data Encryption Standard) ( ) *11 (Entscheidungsproblem),. ( )?,.,., ( ),,,.,,. ( 1936 9 1938 7,,.

6 94, *15., 16,, * , ( ),, 50,, *17. RSA Data Security DES 1999, distributed.net , 2000 DES AES (Advanced Encryption Standard), Rijindael, 2001.,,.,,.,,.,. ( ) :.,,., ,,.,.,., ( III ). 4.,,. (, DES 56, DES 56, 112, 168, AES 128, 192, 256.,, 1024.), IC FeliCa DES AES, (ICOCA, Suica, PiTaPa),, ( Edy, nanako, WAON). IC FeliCa. [31]., LAN AES. 5.?,.,,, *15 DES IBM., 128, DES 56,., (NSA) (1952.,.,,. 2013,, ),?,. *16 56, NSA. *17, DES,.

,,. (, DES 56, DES 56, 112, 168, AES 128, 192, 256.,, 1024.

7 DES, DES,.,.,.,.,, ( III ), *18 3 * (.), A B. p, p m m + pz (Z/pZ) *20 *21 (, ). p, m A B. (.),, p 2., A a, B b, A m a p ( ), ( ), ( ) ( ) r a, B m b p r b. 2 r a, r b., A rb a p, B p. mab p r b a.., p, m, r a, r b., a, b.., RSA,. ( IV ). 2,. *18,, 2. *19 3,,.,.. ( ),.,.,. *20 F, F 0 F F {0 F }, F. F F., Z/pZ (Z/pZ). *21 G, G a, G = {a, a 2, a 3,..., a n 1, a n = 1 G } (, 1 G G ) n, G. (Z/pZ), p = 11, (Z/11Z) = { a + 11Z a = 1, 2,..., 10 }, a + 11Z 11 a ( ), (6 + 11Z) 2 = Z = Z, (6 + 11Z) 3 = Z = Z,,, Z, Z, Z, Z (Z/11Z),.

*19 3,,.,.. ( ),.,.,. *20 F, F 0 F F {0 F }, F. F F., Z/pZ (Z/pZ). *21 G, G a, G = {a, a 2, a 3,..., a n 1, a n = 1 G } (, 1 G G ) n, G.

8 96 III. RSA, 1976 *22,.,,,., 2. (public key),. private key,.,,,.,.,.,..,.,.,.,,..,. (,,.),. 1977,,,, *23 *24, RSA *25 *26. *22 2. MIT,.,. (,.).,.,... *23 3.,. 3,,,., 42,. 43, RSA. *24, RSA.,., RSA ARS.,.,,.,, DNA. *25 RSA (, ). * , RSA,.,,, 1997.,,. 1969,,,.,.,,., 1973,., RSA ,. (,,. 30.),.,. 1980,

, 42,. 43, RSA. *24, RSA.,., RSA ARS.,.,,.,, DNA. *25 RSA. 3 2002 (, ).

9 暗号 97 RSA 暗号誕生の頃の３人, 左からシャミア, リベスト, エイドルマン ( [32, p. 105] から引用 ) そして, 公開鍵暗号現実化に決定的な役割を果たしたのは, 何と, 17 世紀フランスの数学者ピエールドフェルマーが生み出した, 数に関する次のような簡単な定理であった. フェルマーの小定理. p を素数, a を p の倍数ではない整数とするとき, ap 1 1 は p の倍数. この定理は, 初等整数論と呼ばれる代数学の一分野の結果である. 整数論は, その理論の美しさゆえ, 19 世紀ドイツの数学者カールフリードリヒガウスが数学は科学の王女であり, 数論は数学の王女であると称え, 20 世紀イギリスの数学者 G.H. ハーディが著書ある数学者の生涯と弁明の中で, 真の数学は, 戦争にはまったく役立たない. 数論を戦争に利用する方法はこれまで誰も見出してはいないのだと数論の美しさと極端な非応用性をピエールドフェルマー ( 1607 年? 1665 年 ) 誇り高く述べた分野であるが, その分野の古典的な定理が, 現代の情報社会を見えないところで支えているのである. では RSA 暗号の作り方を紹介しよう. 次のような自然数 p, q, s, t を暗号の材料として用意する. (1) p, q : 異なる素数 (2) s : 積 (p 1)(q 1) と互いに素な自然数 (3) t : st 1 が (p 1)(q 1) の倍数となる自然数ピュータの能力が向上し, インターネットが生み出された後, RSA 暗号の特許は莫大な冨をもたらすことになる. また, 公開鍵暗号や RSA 暗号発見の名誉も, 一般的にはディフィー, ヘルマン, シャミア, リベスト, エイドルマンに与えられている.

ハーディが著書ある数学者の生涯と弁明の中で, 真の数学は, 戦争にはまったく役立たない. 数論を戦争に利用する方法はこれまで誰も見出してはいないのだと数論の美しさと極端な非応用性をピエールドフェルマー ( 1607 年? 1665 年 ) 誇り高く述べた分野であるが, その分野の古典的な定理が, 現代の情報社会を見えないところで支えているのである.

10 98, 2 pq s, t., p q. 6. t (p 1)(q 1) ( V ).,.,, p, q, pq 309 ( , pq 1024 ) p, q. p, q, (, [26] ).,, RSA ( ), *27., s (p 1)(q 1), t., pq, s, t. p q, (p 1)(q 1), t., pq,,, p q. (, ( ) *28.) RSA,., RSA. I. A,., A, pq, s *29., ( )., pq t,.,. A, a (,, pq,. a < pq ), a s, pq r. r.. t, r t, pq., a!!!, A. (.),. *27, (, )., 7. *28 0,, 2010 NTT 232. (, RSA.) *29, A,., A,.

11 99. p = 5, q = 7. pq = 35. s (p 1)(q 1) = 4 6 = 24, s = 5. t st 1 (p 1)(q 1) = 24, t = 5., pq = 35 s = 5, t = 5.,. ( ) ,., 26., 26 s = 26 5 = pq = , 31., 31. pq = 35, = t = 31 5 = = ,., 7. RSA, 26 s = 26 5 = , a = 26 s = 5, a s,,., ( ). s = 5, pq = 7 11 = 77, s = n i=0 a i 2 i (, a i 0 1 ) ( 2 ) 53 = = a 53 = a 20 a 22 a 24 a 25., 53, 2 5 = 32.,., a 53 pq = 77.. a 2i 77 a 2i = q i 77 + r i (, 0 r i < 77 ).,

RSA, 26 s = 26 5 = 11881376, a = 26 s = 5, a s,,., ( ). s = 5, pq = 7 11 = 77, s = 53.

12 100 a 53 = a 20 a 22 a 24 a 25 = ( q r 0 )( q r 2 )( q r 4 )( q r 5 ) = r 0 r 2 r 4 r 5 + X (, X 77 )., r 0, r 2, r 4, r 5.,, a 2i,., a 2i+1 = a 2i 2 = (a 2i) 2 = ( q i 77 + r i ) 2 = ri 2 + Y i (, Y i 77 ), r i+1 ri 2 77., s, a s..,.,, a. (,..) ( ),. a ( a < p ) s a s. a s pq, r. ( a s = mpq + r. m, r 0 r < pq ) r t r t. r t pq, r. ( r t = npq + r. n, r 0 r < pq ) r = a ( ), r = a., a st a pq., a st a p q. ( p, q.) a st a p, 2. (I) a p :, a st p., a st a p. (II) a p : t, st 1 (p 1)(q 1)... st 1 = k (p 1)(q 1) (, k ), a p,, a p 1 1 p,

a ( a < p ) s a s. a s pq, r. ( a s = mpq + r. m, r 0 r < pq ) r t r t. r t pq, r. ( r t = npq + r. n, r 0 r < pq ) r = a ( ), r = a.

13 101, a p 1 1 = lp (, l ) a k(p 1)(q 1) = ( a p 1 ) k(q 1) = (1 + lp) k(q 1), 2, a k(p 1)(q 1) = 1 + X (, X : p ).,, a st a = ax. a st = a 1+k(p 1)(q 1) = a a k(p 1)(q 1) = a (1 + X) = a + ax, a st a p., a st a q. a st a pq.. a st a = X (, X : pq ) ( ),. r, a s = mpq + r, r t = ( a s mpq ) t, r t = a st + Y (, Y : pq, pq ) ( )., r = r t npq ( r r t = npq + r ) = a st + Y npq ( ( ). ) = a + X + Y npq ( ( ). ) r = a ( 0 r, a < pq, X + Y npq pq ) ( ) II., A,. ( ), ( ) ( ) *30., pq t, A pq, s., ( ).,., a ( pq,. a < pq ), a t ( ), pq r. r. A. *30 ( ) ( ) ( ), RSA, ( ), ( ).

r, a s = mpq + r, r t = ( a s mpq ) t, r t = a st + Y (, Y : pq, pq ) ( )., r = r t npq ( r r t = npq + r ) = a st + Y npq ( ( ).

14 102 A, s, r s, pq., a!!! ( ) I. A,,. (a s ) t = a st = a ts = (a t ) s ( ) s, t., s, t, t (p 1)(q 1)., t., A.,,.,, pq = 35 s = 5, t = 5 ( ) ,. (1). (2). (3),. (4) 18. IV.,.,,,,,., RSA,.,,.,., 10M ( ), AES (128 ) 1 100M 0.1, RSA 1.

15 103,,,, *31 *32,.,. A. ( ).,. A., 2 A. A,.,,.,. 1 ( ) *33..,,. SSL,. II., A,., ( ),, A. A,,, 2. 2,., ( ) ( 32 ).,, II., A,, A,?., Mr.X Mr.X A, A Mr.X, Mr.X, Mr.X?, A, Mr.X,, Mr.X A?, A Mr.X.,,. (.),, (PKI: public key infrastructure) *31 ( ),, ( ), ( ). (.) 3, 2,,,.,, SHA-1 (Secure Hash Algorithm 1, 160 ) SHA-2. *32,.,,.,,,,. *33,., NSA.

16 104., (TTP: Trusted Third Party) (RA: Registration Authority) (CA: Certificate Authority) *34,,.,,,, ( ), ( ). ( ),.., ( ) (, ),. ( ) *35.. A, A. A,,.,. 2,,.,.,,., OS Web., OS Windows 8, -,,,., ( ).,,, ( ),,,, *36.,,, RSA, PGP. 2014,, 2020, *34,, RA CA. * ,. *36,, 2. (, PGP.) 1,.,,,. 2. ( (fingerprint) ),, (, ),.

17 105 IC. IC, IC,., *37, IC,., IC,, RSA.,.,.,.,, IC.,, IC,.,., (,, ),,.,,. (,,,,.),. 1994,,, Netscape Communication, SSL (Secure Sockets Layer: ) *38. SSL, *39. SSL, ID,,,,,. SSL.. SSL (URI http https *40. ),, ( ) (. Internet explorer ),, ( ).,,., *37,.,. *38 Netscape Communication Netscape Navigator.,,. Microsoft, OS Windows98, Internet explorer, Netscape Navigator. *39 SSL, TLS (Transport Layer Security: ), SSL TLS., SSL TLS SSL. *40 https HyperText Transfer Protocol over Secure Socket Layer (SSL).

),, ( ) (. Internet explorer ),, ( ).,,., *37,.,. *38 Netscape Communication Netscape Navigator.,,. Microsoft, OS Windows98, Internet explorer, Netscape Navigator.

18 106,.,,,..., (DES ). PGP, RSA., RSA., RSA, 2 p, q, (p 1)(q 1) s, t,., RSA,. *41.,,,,,, ( ),,,,,.,, PGP (Pretty Good Privacy). 1991, 1990 *42,. V., RSA,., p, q, (p 1)(q 1),,,, (1760 )., RSA,.,, RSA.,. p, a p, a p 1 1 p., 2 C, p Z/pZ,.,. *41,.. *42,,.,. 3, 1996., ,,,,.

19 暗号 107 (証明) 乗法群 (Z/pZ) の位数は p 1 であり, その任意の元 a + pz ( ここで, a Z ) に対し (a + pz)p 1 = ap 1 + pz は Z/pZ の単位元 1 + pz に一致する. このことから, ap 1 1 pz. つまり ap 1 1 は p の倍数である. (証明終) ここでの素数 p を任意の自然数 n に拡張した結果が, 次に紹介するオイラーの定理である. そこにはオイラー関数と呼ばれる概念が使われている. まずこれを定義しよう. n を自然数とせよ. 1, 2,..., n の中で, n と互いに素なものの個数を φ(n) で表し, オイラー関数とよぶつまり, φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6,. 特に, n が素数 p であるときを考えると, 1, 2, 3,..., p 1 がすべて p と互いに素なので φ(p) = p 1 であることが分かる. これを用いて, フェルマーの小定理は次のように一般化される. レオンハルトオイラー ( 1707 年 1783 年 ) オイラーの定理 n を自然数, a を n と互いに素な整数とするとき, aφ(n) 1 は n の倍数. (証明) X を n と互いに素な 1 以上 n 1 以下の自然数の集合とすると, 剰余環 Z/nZ の単元群 *43 U (Z/nZ) は { a+nz }a X に他ならない. ( a と n が互いに素であることは, 整数 k, l で ka+ln = 1 を満たすものが存在することと同値であることから分かる. ) よって, U (Z/nZ) の位数は X の元の数, つまり φ(n) である. したがって, X の任意の元 a に対し, (a + nz)φ(n) = aφ(n) + nz は U (Z/nZ) の単位元 1 + nz に一致する. ゆえに, aφ(n) 1 nz. つまり, aφ(n) 1 は n の倍数. (証明終) そして, オイラー関数は次の定理の (1) ように具体的に計算でき, これを用いると次の定理の (2) (積公式) が得られる. オイラー関数の公式 (1) n = p1e1 pe22 perr を自然数 n の素因数分解とするとき, ( )( ) ( ) φ(n) = n p1 p2 pr と表される. (2) 自然数 m, n に対し, これらが互いに素であることと, φ(mn) = φ(m) φ(n) が成り立つことは同値である. 証明. まず, n = pe ( p : 素数 ) の場合を考えよう. a { 1, 2,..., n } に対して, a と n は互いに素ではないことと, a が p の倍数であることは同値である. そして, { 1, 2,..., n = pe } の中で p の倍数は, p 1, p 2, p 3,..., p pe 1 = pe = n *43 環 R に対し, 乗法に関する逆元をもつ元を単元と呼ぶ. そして, R の単元全体の集合は R の乗法に関して群をなす. この群を単元群と呼び, 通常 U (R) で表す. 特に R が体のとき, U (R) は乗法群 R に他ならない.

.., n の中で, n と互いに素なものの個数を φ(n) で表し, オイラー関数とよぶつまり, φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6,. 特に, n が素数 p であるときを考えると, 1, 2, 3,..., p 1 がすべて p と互いに素なので φ(p) = p 1 であることが分かる.

20 108 p e 1., φ( p e ) p e, ( φ( p e ) = p e p e 1 = p e 1 1 ) p, n = p e 1 1 pe 2 2 pe r r., Z/nZ ( Z/p e 1 1 Z ) ( Z/pe 2 2 Z ) ( Z/per r Z ), a+nz ( a+p e 1., φ(n) = U( Z/nZ ) = p e 1 1 p e Z, a+pe 2 2 = U( ( Z/p e 1 1 Z ) ( Z/pe 2 2 Z ) ( Z/pe r r Z ) ) = U( Z/p e 1 1 Z ) U( Z/pe 2 2 Z ) U( Z/pe r r Z ) = U( Z/p e 1 1 Z ) U( Z/pe 2 2 Z ) U( Z/per r Z ) = φ( p e 1 1 ) φ( pe 2 2 ) φ( per r ) ( ( ) ) ( ( ) ) ( ( ) ) 1 1p1 1 1p2 1 1pr = n ( 1 1p1 ) ( 1 1p2 ) ( 1 1pr ) p e r r Z,, a+per r Z ) (2) m, n m = p e 1 1 pe r r, n = q f 1 1 qf s s., m, n : {p 1,..., p r } {q 1,..., q s }. ( ) ( ) ( ) 1 1p1 1 1pr 1 1q1 φ(mn) = mn ( 1 1qs ) ( ) φ(mn) = φ(m) φ(n), p, q, ( ( φ(pq) = φ( p) φ( q) = p 1 1 )) ( q p ( 1 1 q )) = (p 1)(q 1)., RSA (p 1)(q 1), pq φ(pq).,. (1) a, a st pq, a ( RSA ) (2) RSA, s, t (p 1)(q 1). ( ), p, q, s, t. (3), s, t, t st 1 (p 1)(q 1) s, t (p 1)(q 1)., p, q, t, s, RSA.

r Z ) = φ( p e 1 1 ) φ( pe 2 2 ) φ( per r ) ( ( ) ) ( ( ) ) ( ( ) ) 1 1p1 1 1p2 1 1pr = n ( 1 1p1 ) ( 1 1p2 ) ( 1 1pr ) p e r r Z,, a+per r Z ) (2) m, n m = p e 1 1 pe r r, n = q f 1 1 qf s s.

21 109,, (1), a pq. ( a pq, a p q,.) ( ), (i), (ii), (iii). (i) (ii) (iii) st = 1 + φ(pq)u u, s, t. s + φ(pq)z t + φ(pq)z, U(Z/φ(pq)Z). a φ(pq) = 1 + pqv v,. (i) : t, st 1 (p 1)(q 1) = φ(pq)., st + φ(pq)z = 1 + φ(pq)z ( )., u. (ii) : s, (p 1)(q 1) = φ(pq). s + φ(pq)z U( Z/φ(pq)Z )., ( ), U( Z/φ(pq)Z ), ( s + φ(pq)z )( t + φ(pq)z ) = 1 + φ(pq)z ( : U( Z/φ(pq)Z ) )., (ii). (iii) :, a pq, a φ(pq) 1 pq. v. (1) a st = a 1+φ(pq)u ( (i) ) = a 1 (a φ(pq) ) u = a ( 1 + pqv) u ( (iii) ) = a + X (, X pq ) a st pq a. ( a < pq ) (2), (3) (ii). ( ) VI., RSA, Taher Elgamal. Z/pZ, s + pz (Z/pZ) ( p, (Z/pZ), s ), t + pz (Z/pZ), (s + pz) m = t + pz m (m )., m (s + pz) m..

22 110. p, s, m. p, s p 1 ( s + pz (Z/pZ) ), m p 2., s m p r, (p, s, r), m. a (, a < p ), p 1 t 2 (c 1, c 2 ). { c1 : s t p c 2 : a r t p, (c 1, c 2 ). s + pz (Z/pZ) ( : ) c 1 0., 1 c 1 p 1., p, c 1 p, u, v uc 1 + vp = 1., u m c 2, a. (.,.) ( ) s m = pq + r, s t = pq 1 + c 1, a r t = pq 2 + c 2., u m c 2 = u m (a r t pq 2 ) ( a r t = pq 2 + c 2 ) = u m (a (s m pq) t pq 2 ) ( s m = pq + r ) p = a u m s mt + X (, X : p, p ) = a u m (pq 1 + c 1 ) m + X ( s t = pq 1 + c 1 ) = a u m c m 1 + Y (, Y : p ) = a (1 vp) m + Y ( uc 1 + vp = 1 ) = a + Z (, Z : p ) u m c 2 p a ( a < p ) ( ) 1985 IBM., (Z/pZ), p K., p 5 y 2 = x 3 + ax + b (, a, b K 4a b 2 0 ), x y 0 := (, )., E(K) := { (x, y) K 2 y 2 = x 3 + ax + b } {0}, 0. (Z/pZ) p, a, b, p., (Z/pZ) 300, 50.,.,.

23 111 VII.,. (.. ( ),. ( ),.,. ( ). ( ),.,,,.,,. ( ),.,.,,. ( ),,. ( ) RSA,,. ( ) RSA,.. ( ),,. ( ),. ( ).,. ( ),. ( ). ( ),,. ( ),. ( ),. ( ),.,,,,.. ( ),.,,,. ( ),,,,. ( ).,. ( ),.. ( )

24 112 RSA,,.,,.,,. ( ),,,, RSA.,.. ( ),,. ( ),,,., ( ). ( ),,.,. ( ) (4), -!!. ( ). ( ). ( ) VIII., RSA.,,.,,,.,,,,.,, RSA ( ) *44..,.,,.,,, ,,.,,.,.,,.,,., ( ), ( ), ( ).., * AT&T,,, RSA.

25 113,..,,,,.,,.. [1],,, 2010, [2], 14, 1962, [3] S.C.,, RSA, 2001, [4] Elgamal, T., A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory IT-31 N.4 (1985), [5],, PGP, 1997, [6],,, 2014, PHP [7] Hilton, P., Cryptanalysis in World War II and Mathematics Education, The Mathematics Teacher 77 No.7 (1984), [8],, 2004, [9],!, 2013, [10],?, 1995, [11],,,, 1967, [12],,, 2001, [13] N.,,, 1997, [14],,, 2010, [15],, 2014, KK [16],, 9, 2012, BP [17],,, 2001, [18],, 1098 (1999), [19],, 2003, [20], , 2008, [21],, 2005, [22],,?, 2005, [23],,,,,,, 2012, BP [24] Rivest, R.L., Shamir, A., Adleman, L.M., A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Comm. of ACM 21,2 (1978), [25],,, 2013, [26] H,, 3, 2007, [27],,, 2001, [28],,, 2014, [29],, 2014, [30] S, J,,,,,,, - 5, 2013, BP [31],,, 2010, [32],, 2008, [33] H.O.,,, - -, 1999, [34],, 2003,

( )

( ) NAIST-IS-MT0851100 2010 2 4 ( ) CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i On the Key Management Policy of Challenge Response Authentication Schemes Toshiya