44 2015 89 2015 3 31 2014, RSA, 17,. (,,.),,.,,, RSA, RSA, RSA.,,, RSA I. 1.,, (,,, 3 ),., IC ( IC ),.,.,,.,.,. ( ) :. :. :,. (, ( ) ) :,. :,. (,, 3.) II.. (,.),.,., (, ),., 3
馬 場 良 始 90 平文 : book 暗号文 : errn となる. 単純に文字をずらすシーザー暗号は改良され, 文字の置き換え表を作り, それに従って暗号化 復 号をする換字式暗号が作られた. しかし, ある文字を単に別の文字に置き換えるような換字式暗号 は, 頻度分析により簡単に解読される. たとえば英語だと e や t といった文字の使用頻度が高い the という単語がよく使われる, tion のような綴りのパターンが多用される などの, 元の言語が持っている特徴が暗号文の中に残ってしまうので, それを手がかりにして解読 されてしまう *1. 頻度分析法が発達し, 単なる換字式暗号の安全性が低下したので, 16 世紀頃, 言語の特徴を暗号 文に (ほとんど) 出さない新たな換字式暗号であるヴィジュネル暗号が考案された (詳細は, 例えば [27] 参照). この暗号は非常に安全性が高く 解読不能の暗号 とも呼ばれたが, 1863 年に暗号文か ら言語の特徴を見いだす方法が見つけ出され破られてしまった. この間, 18 世紀には, ヨーロッパ の列強各国が, 他国の通信文の入手 解読を行う ブラック チェンバー と呼ばれる国家秘密情 報機関を作るようになったり, 19 世紀中頃には, 電信が実用化されて, 通信文は傍受 解読される ものとして, 暗号を用いるのが常識となったりした結果, 安全な暗号の必要性はさらに高まった. さらに 19 世紀末には無線が発明され, 電線を引くことなく地球上のどことでも通信が可能 (傍 受も可能) になった. ほぼ同時期に第 1 次世界大戦が勃発し, 安心して無線で通信できる強力な暗 号の開発が急務となったが, 生み出された暗号は, 短期間の間に解読されるか, 実用性がないかのいず れかであった. 第 1 次世界大戦後, 容易に破られない暗号解読技術を求 めて, さらに複雑な手順の暗号が次々に考案された. そし て, そのような複雑な手順を簡単な操作で間違いなく行う ために, 機械式の暗号機が作られるようになった. このよ うなものの中で, 歴史上特に有名なものに, 第 2 次世界大 戦中にドイツ軍が使用していたエニグマ暗号機がある. 解 読されない強い暗号を求めて, さまざまな暗号システムが 考え出された中で, 換字のしくみをもっと複雑にし, さらに １文字ごとに暗号化手順を変えるという, 当時おそらく最 強の暗号システムであり, しかも鍵は毎日変更された. 暗 号機は持ち運び可能なタイプライター型で, 1 兆を越す暗 号鍵を簡単に設定 選択でき, 暗号文の復号も同じ暗号機 でできた. 第１次世界大戦の結果, 再び独立国となったポーランド は, 国家維持のために隣国であるドイツ, ロシアの通信暗号 エニグマ暗号機 を解読し続ける必要に迫られていた. 暗号解読は, 国家の ( [21] から引用 ) 存続を賭けた最重要課題であったのだ. そして, 1930 年代に, ドイツ軍が絶対の自信を持っていた エニグマは, ポーランド暗号局に所属していた数学者マリアン レイェフスキによった破られるこ *1 このような解読手法は, エジプトのヒエログリフ, バビロニアの楔形文字, 古代トルコのルーネ文字, インドのブラー フミー文字などの古代文字解読にも使われた.
91 *2.. 1938,,., 1939 4,.,,.,,, 1939 7 *3., 1939 9,, 2., U,.,,, (, 7 ), (. ), ( ).,,,., 2,,. 1.,, 3 /. 2,,., *4.,, 1974., 2, *5., 2,., 3 (,, ),,, 1935 2,.,,, *6 *7., *2,,, 3. 3 1,,. *3,. *4,., 3., DES, (NSA), PGP 1990, RSA,,,,.,,., 1974.,. *5,,.,,. *6. *7.,
92 The Ten Pointed-Note ( ), *8., *9,,, (, ),., *10. 2. 2,., (,,,, ).,,.,,.,. 1968. (, [27, V ] ) 2,,. 3. 1,.,,, 1936 On Computable.,.,,,,,.,,,,. *8,, Gerald Nye (Nye Committee, 1934 4 ),,,, ( ),., 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,.
93 Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc. (1936), 230 265 *11.,,, ( ),, ( ).,,., ( ), *12.,,,,,,.,., (. 2 ), EDVAC (Electronic Discrete Variable Calculator) ( EDVAC ),, 1945., EDVAC., EDVAC,, 1949 *13 EDSAC (Electronic Delay Storage Automatic Calculator) *14. 13.,., 1959 IC, 1960,.,,,.,,., 1977 (NBS), IBM DES (Data Encryption Standard) ( ) *11 (Entscheidungsproblem),. ( )?,.,., ( ),,,.,,. ( 1936 9 1938 7,,.,,,.,,.) *12, (,. ). *13, 1946, EDVAC. *14, EDSAC 1948 6, Baby Mark I., (, ),, 1948 9 Mark I,.
94, *15., 16,, *16. 1994, ( ),, 50,, *17. RSA Data Security DES 1999, distributed.net 22 15., 2000 DES AES (Advanced Encryption Standard), Rijindael, 2001.,,.,,.,,.,. ( ) :.,,.,.. 1976.,,.,.,., ( 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,.
95. 1976 DES, DES,.,.,.,.,, ( III ), *18 3 *19. 1976. (.), 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 = 6 2 + 11Z = 3 + 11Z, (6 + 11Z) 3 = 6 3 + 11Z = 7 + 11Z,,, 2 + 11Z, 6 + 11Z, 7 + 11Z, 8 + 11Z (Z/11Z),.
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. 3 2002 (, ). *26 1997, RSA,.,,, 1997.,,. 1969,,,.,.,,., 1973,., RSA.. 30..,. (,,. 30.),.,. 1980,
暗号 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 暗号発見の名誉も, 一般的にはディフィー, ヘルマン, シャミア, リベスト, エイドルマンに与えられ ている.
98, 2 pq s, t., p q. 6. t (p 1)(q 1) ( V ).,.,, p, q, pq 309 (2 1024 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,.
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.,. ( ) 0 1 2 3 4 5 6 7 8 9,., 26., 26 s = 26 5 = 11881376 11881376 pq = 35 31., 31., 31. pq = 35, 26.. 11881376 = 35 339467 + 31 31 t = 31 5 = 28629151 28629151 = 35 817975 + 26,., 7. RSA, 26 s = 26 5 = 11881376, a = 26 s = 5, a s,,., ( ). s = 5, pq = 7 11 = 77, s = 53. 53 n i=0 a i 2 i (, a i 0 1 ) ( 2 ) 53 = 1 + 0 + 4 + 0 + 16 + 32 = 1 2 0 + 0 2 1 + 1 2 2 + 0 2 3 + 1 2 4 + 1 2 5 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 ).,
100 a 53 = a 20 a 22 a 24 a 25 = ( q 0 77 + r 0 )( q 2 77 + r 2 )( q 4 77 + r 4 )( q 5 77 + 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,
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, ( ), ( ).
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 ( ) 0 1 2 3 4 5 6 7 8 9,. (1). (2). (3),. (4) 18. IV.,.,,,,,., RSA,.,,.,., 10M ( ), AES (128 ) 1 100M 0.1, RSA 1.
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.
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. *35 2001,. *36,, 2. (, PGP.) 1,.,,,. 2. ( (fingerprint) ),, (, ),.
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).
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., 1994 1996,,,,.
暗号 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 の素因数分解とするとき, ( )( ) ( ) 1 1 1 φ(n) = n 1 1 1 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 に他ならない.
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 2 2 1 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.
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,.. 1984 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..
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 3 + 27b 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.,.,.
111 VII.,. (.. ( ),. ( ),.,. ( ). ( ),.,,,.,,. ( ),.,.,,. ( ),,. ( ) RSA,,. ( ) RSA,.. ( ),,. ( ),. ( ).,. ( ),. ( ). ( ),,. ( ),. ( ),. ( ),.,,,,.. ( ),.,,,. ( ),,,,. ( ).,. ( ),.. ( )
112 RSA,,.,,.,,. ( ),,,, RSA.,.. ( ),,. ( ),,,., ( ). ( ),,.,. ( ) (4), -!!. ( ). ( ). ( ) VIII., RSA.,,.,,,.,,,,.,, RSA ( ) *44..,.,,.,,, 20 50.,,.,,.,.,,.,,., ( ), ( ), ( ).., *44 1994 AT&T,,, RSA.
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), 469 472 [5],, PGP, 1997, [6],,, 2014, PHP [7] Hilton, P., Cryptanalysis in World War II and Mathematics Education, The Mathematics Teacher 77 No.7 (1984), 548 552 [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), 138 146 [19],, 2003, [20], 1919 1946, 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), 120 126 [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,