理論

2010年04月07日

インターネット通信における暗号では、主として公開鍵暗号方式が使われている。
この暗号化方式では、大きな数の素因数分解は容易ではないことが暗号強度の数学的根拠になっている。

任意に決めた2つの素数の積をとり、その積の数値が第三者に分かっても、元の素数を算出するには時間がかかる性質を利用している。
コンピュータ上の暗号化に関する設定では、公開鍵と秘密鍵の鍵ペアを作成し、公開鍵は誰に知られてもよく、秘密鍵は知られてはいけないファイルとして保存される。
数学的な素数の原理と、公開鍵および秘密鍵との関係をよく理解していなかったので、改めて数学的な原理を元に、鍵の意味について勉強した。

一般的に使われるRSA暗号を例にとり、手計算で暗号化と復号化をシミュレートすることにする。

実際の計算においては、ユークリッドの互除法をはじめ、なかなか難しい話が多いので、ここでは「どうしてそうなのか」といった理屈には踏み込まない。(踏み込めない)(笑)
気になる方は、以下の参考リンクを読み込んでください。
表面的な流れのみを、できるだけ容易に整理してみる。 厳密な表現から外れることはもとより、誤解や誤りもあるかもしれない。
プログラミングしようにも、巨大な数を多倍長整数で扱うなり、特殊なアルゴリズムが必要だったりと、実装は大変そうである。暗号化には計算コストがかかる、というのもよくわかる。

1.参考リンク

2.鍵の作り方

(1)素数の決定

    ふたつの異なる素数p,qを決める。

(2)2つの素数の積(n)を求める

    n=pq

(3)最小公倍数(u)を求める

    (p-1)と(q-1)の最小公倍数を求める。
    これをuとする。
    (面倒なら u=(p-1)(q-1) でもいい)

(4)uと素な数(d)を決める

    uとの最大公約数が1となるdを求める。
    つまりdは、uと共通の約数を持っていない数値のこと。
    dの候補は複数あるが、その中から任意に決める。

(5)eを求める

    eにdをかけて、uで割った時、余りが1となるようにする。
    eの候補は複数あるが、その中から任意に決める。

(6)鍵の完成

    公開鍵は、nとe
    秘密鍵は、nとd

2.暗号化

    送信者が受信者の公開鍵n,eで平分Mを暗号化し、暗号文Eを作る。
    平文メッセージMは公開鍵nより小さくなければならない。
    暗号文Eは以下のように求める。

    E= [M^e をnで割った余り]

3.復号化

    2で暗号化された暗号文Eを、正規の受信者が自分の秘密鍵dを使って復号化し平文Mを求める。

    M= [ E^d をnで割った余り ]

4.結論

    公開鍵と秘密鍵は、大きな数の素因数分解においてどんなものなのかと捉えると、誤解を恐れずに大胆に言えば、余りをハッシュという考え方で置き換えて。

    秘密鍵:素数同士の積と元になった素数のハッシュ値
    公開鍵:素数同士の積と秘密鍵のハッシュ値

    専門家からはクレームつきそう・・・。

    実際の鍵ファイルは、テキストファイルである。これは、上記の値をbase64エンコードし、扱いやすくしている。


以下が手計算で流れを追ってみた結果。

(1)素数(p,q)を決める

    p = 7
    q = 23

(2)積(n)を求める

    n= 161

(3)最小公倍数(u)を求める

    u= 66

(4)uと素の数(d)を求める

    u= 66 を素因数分解をすると。

    1,2,3,6,11,22,33,66

    もしd= 2なら、uとdの最大公約数2
    もしd= 3なら、uとdの最大公約数3
    もしd= 4なら、uとdの最大公約数2
    もしd= 5なら、uとdの最大公約数2
    もしd= 6なら、uとdの最大公約数6
    もしd= 7なら、uとdの最大公約数1
    もしd= 8なら、uとdの最大公約数2
    もしd= 9なら、uとdの最大公約数3
    もしd=10なら、uとdの最大公約数2



    そこで、 d=7 とする。

(5)eを求める

    もしe= 1なら、ed= 7それをu=66で割って余り7
    もしe= 2なら、ed=14それをu=66で割って余り14
    もしe= 3なら、ed=21それをu=66で割って余り21
    もしe= 4なら、ed=28それをu=66で割って余り28



    もしe=10なら、ed=70それをu=66で割って余り4
    もしe=11なら、ed=77それをu=66で割って余り11
    もしe=12なら、ed=84それをu=66で割って余り18



    もしe=18なら、ed=126それをu=66で割って余り60
    もしe=19なら、ed=133それをu=66で割って余り1
    もしe=20なら、ed=140それをu=66で割って余り8



    そこで、e=19 とする。

(6)鍵の完成

     

    公開鍵 n=161, e=19
    秘密鍵 n=161, d=7

     

(7)暗号化

    平分Mを10とし、これを暗号化する。

    E= [ 10^{19}n=161 で割った余り ]

    (10^19)
    =(10^9)^2*10
     =((10^3)^3)^2*10
     =(1000^3)^2*10

    -->1000をn=161で割った余りを求めると、34

     (34^3)^2*10
     =39304^2*10

    --> 39304をn=161で割った余りを求めると、20

     20^2*10
     =4000

     

    --> 4000のn=161で割った余りは136

    暗号文E=136である

(8)復号

    暗号文E=136を、秘密鍵d=7で復号し、平文Mを求める。

    M= [ 136^7n=161 で割った余り ]

    136^7
     =(136^2)^3*136
      =18496^3*136

    --> 18496をn=161で割った余りを求めると、142

    142^3*136
     =2863288*136

    --> 2863288をn=161で割った余りを求めると、64

    64*136
     =8704

     

    --> 8704をn=161で割った余りを求めると、10

    平分Mは、M=10である。

    送信者の平文Mと一致し、めでたく復号できた。



sylphide_ffr31mr at 20:20コメント(0)トラックバック(0) 
記事検索
最新コメント
livedoor プロフィール
月別アーカイブ
  • ライブドアブログ