2019.03.05 [学習メモ] RSA暗号

いつも分かった気になって、また説明できなくなるので、自分の学習記録のためのメモ。
参照: http://tsujimotter.hatenablog.com/entry/rsa

---

• 平文P,　暗号文C、暗号鍵k、公開鍵m
  • 暗号鍵k, 公開鍵mは公開される
• 暗号化
  • (1) P^k≡C(mod m)
• 復号鍵 uが存在し、
  • (2) C^u≡P(mod m)
• (1)を(2)に代入すると
  • (3) (P^k)^u≡P(mod m)
• 公開鍵m=p・q (ただし、p, qは十分に大きな素数)
• 重要なポイント
  • 都合の良い復号鍵uが存在する
  • そして、その復号鍵uは、秘密鍵p,qから計算可能
  • 復号鍵uは、暗号鍵k, 公開鍵mからは計算不能
• 暗号鍵k, 公開鍵mの存在可能性
  • オイラーの定理
    • 正の整数 a, mに対し、a, mが互いに素であるとき、
      • (4) a^φ(m)≡1 (mod m)
    • が成り立つ。φ(m)はオイラー関数
    • オイラー関数φ(m)の定義
      • mより小さい正の整数のうち、mと互いに素な数の個数。
        • e.g. m=10 ==> φ(m)=4 {1,3,7,9}
    • mが素数pであれば、φ(p)=p-1
      • フェルマーの小定理
  • (4) のaにPを代入し、両辺をv乗する
    • (5) P^{φ(m)・v｝≡1 (mod m)
  • さらに両辺にPをかけると
    • (5) ‘P^{φ(m)・v+1｝≡P (mod m)
  • 式(3)と比較すると
    • (6) k・u=φ(m)・v+1
    • (6)’ k・u-φ(m)・v=1
  • 式(6)を満たすu, vが存在し、u>0であればよい。
  • 一時不定方程式の整数解の定理
    • a, bを互いに素な整数としたとき、
      • au+bv=1
    • を満たす整数解、u,vが存在する
  • m=pqのとき、オイラー関数φ(m)=(p-1)(q-1)
    • 素因数分解できるから計算可能
  • φ(m)が分かれば、(6) にユークリッドの互除法を使ってuを見つけることが出来る
    • 再掲：　(6)’ k・u-φ(m)・v=1
      • φ(m)　は known
      • kをφ(m)に互いに素になる様に選ぶと、、、
  • 拡張ユークリッドの互除法
    • a,bの最大公約数をdとして、ユークリッドの互除法の逆をたどることでax+by=dとなる整数x,yを全て求めることができる。これはa,bが互いに素、つまりd=1である時に特に有用。
    • これを使って、u, vを決定できる。