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を決定できる。

 

  • kotsuking
  • 理研・計算科学研究センター研究員、文部科学省卓越研究員、気象予報士。
    京都大学大学院で博士(工学)を取得。
    スーパーコンピューターを駆使して天気予報の改善に取り組むデータ同化研究者。
    座右の書は「7つの習慣」。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です