暗号(RSA暗号)について





暗号とは、第三者に情報が知られないようにするため、情報を特別な知識なしでは読めないように変換することです。 送信者は情報を暗号化し、受信者は情報を逆変換することにより、送信者の情報を読むことができます。
もしもこの暗号化がなかったら、大混乱です。 たとえば、クレジットカードで支払うと、クレジット番号はPOS経由で決済業者に届くので、途中で第三者がデータを盗み取りができたならば、他人の名義(口座)で取引が可能になります。その他に、インターネット上の取引もできません。インターネット上のID・パスワードも意味がありません。また、暗号化してもその方法が簡単に解読できてしまえば意味がありません。
暗号化の方法は歴史的に見てもさまざまありますが、ここでは、共通鍵暗号を簡単に、そして公開鍵暗号をわかりやすく説明します。

[共通鍵暗号]
送信者は情報を鍵(変換方法)で暗号化し、受信者は情報を同じ鍵で逆変換することにより送信者の情報を読むことができます。 第三者が鍵を知ってしまえば暗号になりません。 第二次世界大戦での暗号エニグマ(ドイツ)・パープル(日本)が、連合国に解読されていたので暗号になってませんでした。

[公開鍵暗号]
送信者は情報を公開鍵(変換方法)で暗号化し、受信者は情報を秘密鍵で変換することにより送信者が情報を読むことができます。 第三者が公開鍵と暗号化された文を知り得ても、そこから情報を知ることができないようにする方法です。
受信者は、POS業者やインターネットソフト開発業者に「この公開鍵で暗号化してください」と言うことができるようになります。

[公開鍵暗号の簡単な例]
素数11と13の積と互いに素の数たとえばe=53を使い、公開鍵を143,53とします。 通常は大きな素数p,qを選びを計算し数百桁に、eも大きな素数にします。 あらかじめ、で割ったときの余りが1となるようなd=77を定めます。 秘密鍵は77になります。 送信者は、情報16から16を53乗し、143で割った余り48を求め送信します。 仮に第三者が、公開鍵143,53と暗号化された文48を知り得ても、本来は大きな素数を使っているため、そこから情報16を知ることができません。 受信者は、48を77乗し143で割った余りを求め、元の情報16を知ることができます。

[自然数の性質]
を自然数とする。で割ったとき、商が余りがとする。 これを数式で書くと、
を満たす自然数が存在する。」
と書く。 は合同」と言う。

[合同の性質]
(1)
    (@)
    (A)
    (B)
(2)
    ならば
    (@)
    (A)
    (B)
    (C)

[定理]
を自然数で互いに素であるとき、

を満たす整数が存在する。

[Fermatの小定理]
を素数、で割り切れない自然数とすると、


[Fermatの小定理の拡張]
を素数、で割り切れない自然数とすると、


[公開鍵暗号の原理]
公開鍵暗号の原理は、数学の素数の性質を使います。
を原文、を素数、素数の積と互いに素の数とする。
を満たす整数が存在する。
送信情報をとする。
受信側は上記から、で原文を知ることができます。なぜなら、

                
                
                
                

[第三者が解読できない理由]
第三者が情報を知り得たとします。 解読するための鍵を得るためには、まず数百桁の数から2つの素数を探さなければなりません。 ただ、いくらスーパーコンピュータでも数百年?かかるので、現実的に不可能です。鍵を探すことは不可能です。

[今後]
スーパーコンピュータも高速になり、解読時間が数時間になるかもしれません。 そのときには、素数桁数が数千桁になったり、素数2個の積から3個の積になったりして、どんどん複雑になると思います。

[繰返し自乗法]
最初の例にあった「16を53乗し、143で割った余り」を計算するには、通常のコンピュータの自然数の扱える制限を越えてしまうため、効率よく計算する方法が必要です。 それが繰返し自乗法です。 例で計算すると、まず53を2進法で分解します。

次にを順次計算します。





上記値を引用し、

      
      
      

[数百桁の計算]
数百桁の数字の計算ですが、通常ではコンピュータの有効桁数は通常十数桁なので、計算できません。 計算方法は、私のサイト「数字の桁数1000桁のたし算」を参考にしてください。

不等式 関数 図形と方程式 軌跡と領域 微積分―整関数 公式集

「こだわりハウス」写真館| 数学公式集| ピンポイントストリートビュー| FaceBook|