素数と暗号

素数 については多くの興味のある話題がありますが,
ここでは 暗号 との関係について書いておきます。

暗号と言えば, 戦争につながる暗い話を想像しがちですが, 現在のように 計算機が発達した時代では, 暗号が日常的に使われています。 例えば、情報通信, 電子マネー, インターネット上の商取引等です。 参考として, 朝日新聞 1997. 6. 15 (日) 8 面をご覧下さい。

そこで、ここではインターネットで利用されている暗号の基礎となっている RSA (Rivest,Shamir and Adelman) 暗号について述べたいと思います。

整 数

数 1, 2, 3, ... を 自然数 と言います。 自然数 a, b, c に対し, a = bc の時 b は a の 約数 a は b の 倍数 と言います。 a, b に共通の約数が 1 以外にないとき 互いに素 と呼びます。 また 数 p の約数が 1 または p のみであるときpを 素数 と呼んでいます。 自然数 n と整数 a, b に対し, a - b が n で割れるとき a と b は n を法として合同 であるといい,

a ≡ b mod n
と書きます。 このような式を 合同式 と言います。

例.


17 ≡ 3 mod 7

次の枠に数字をいろいろ入れてみて下さい。(JavaScript使用)

≡ mod 7
合同式には次のような性質があります。 証明も簡単ですので皆さんで、試みて下さい。
a ≡ b, c ≡ d ⇒ a + b ≡ c + d , ab ≡ cd

暗 号

ある意味のあるデータを他人が判別できないように、そのデータを変換する事を 暗号 と呼んでいます。 実際に、ある文章を暗号にする時、計算機では、まず 文字と数字の間に 1 対 1 の対応を付けておきます。 そしてこの数字を、ある式を用いて変換することで他人が判別できない データができあがるわけです。ですから、インターネット上で 実際に送る暗号はは, 数字を並べた物になります。

鍵の設定

暗号は、よく金庫に例えられます。 金庫にものを入れて鍵を掛けてしまえば、もう他人がその中のものを 見る事は、できません。 RSA暗号では、２つの鍵を用意します。１つは、金庫を閉める鍵で、公開鍵と 呼ばれます。もう１つは、金庫を開ける鍵で、非公開の鍵です。

巨大素数(百桁くらい) p, q に対し, n = pq とします。
(p-1)(q-1) と互いに素な自然数 k に対し, 次の合同式を満たす k' が比較的簡単な計算( Euclid 互助法 )で求まります。

kk' ≡ 1 mod (p-1)(q-1)
ここで、 数 n, k が(公開)鍵で、 素数 p, q は秘密です。。 暗号を解読する(金庫を開ける)側の鍵が n と k' です。

暗号による文の伝達

まず文 S が与えられたらそれを数字の集合 T に変えます。 この変換の仕方は送付先が知っているかまたは知らせておきます。 T = {a, b, c, ..., d} に対し、 公開鍵 n, k を使って

w ≡ ak, x ≡ bk, y ≡ ck, ... , z ≡ dk mod n
Tk = { w, x, y, ..., z } を送付先へ送ります。 送られた側では 非公開の鍵 n, k' を用いて
a ≡ wk', b ≡ xk', c ≡ yk', ... , d ≡ zk' mod n
T = (Tk)k' を得ることになります。 この T から以前と逆の手続きで文 S が復元されます。

理由

それでは、どうしてこれでうまく復元できるかについて説明しましょう。
Fermat の小定理 から一般に

a(p-1) ≡ 1 mod p, a(q-1) ≡ 1 mod q
となることが知られています。 この２つの式から
a(p-1)(q-1) ≡ 1 mod n
となるので, a ∈ T に対し,
wk' ≡ (ak)k' = akk' ≡ a mod n
が成り立つわけです。

RSA の実例

では、実際に暗号を作ってそれを元の文章に復元してみましょう。
各アルファベットは次のように数字を対応させ簡単のため空白は、 考えない事にします。

A B C D E F G H I J K L M
00 01 02 03 04 05 06 07 08 09 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

また、鍵を作るための数字は、次のように決めます。
n = 2537 = 43 × 59, k = 13, k'= 937

(ここで 43, 59 は素数)

S : PUBLIC KEY CRYPTOGRAPHY
T : 1520 0111 0802 1004 2402 1724 1519 1406 1700 1507 2423
Tk : 0095 1648 1410 1299 0811 2333 2132 0370 1185 1957 1084
(Tk)k' : 1520 0111 0802 1004 2402 1724 1519 1406 1700 1507 2423
S : PUBLIC KEY CRYPTOGRAPHY

T での最後の数 2423 の 23 は文字 X を表しますがこれはダミーです。

この暗号解読の鍵を握るのは、まさに数 n の因数分解なのですが、 実際に使われている n は 200 桁くらいの整数でそれを 二つの素数に素因数分解するには一般に現在(1998)の最も高速な計算機で, いかに早く見積もっても, 10 年はかかると思います。

このことが、この暗号の安全性を保証している事になります。

数 のホームページにもどる。