『暗号技術入門』読書メモ

プログラミング

cr.hyuki.net

少し前に『暗号技術入門』（第1部、第2部）を読んだので読書メモを残しておきます。

第2章

シーザー暗号

  • 文字ずらしで暗号化する方法

  • シーザー暗号をRubyで書くと、、を考えてみた。

    • 自分で考えた方法（nextを使う）
class String
  def encrypt_text(shift_int)
    splited_str = chars
    shift_int.times do
      splited_str.each { _1.next! }
    end
    splited_str.join
  end
end

puts '123あいうえおABC'.encrypt_text(3)
#=> 456ぅぇぉかきDEF
  • chatGPT先生に聞いたところ、アルファベット限定だが、rotateとtrを使う方法が返ってきた。なるほどー。
def shift_string(str, shift)
  alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  shifted_alphabet = alphabet.chars.rotate(shift).join
  str.tr(alphabet, shifted_alphabet)
end

puts shift_string("ABD", 3)
#=> "DEG"

単一換字暗号の解き方

  • 単一換字暗号とは、文字を不規則に1対1で置き換える方法（aはc, bはf, cはiなど）
  • 組み合わせはアルファベットだと26 * 25 * .. * 1の403291461126605635584000000通りあり、一見解析は困難に思える
  • しかし、頻度分析（アルファベットだとtheなどが多く、推測しやすい。また、頻度が少ないものもヒントになる。）を使うと、単純計算では組み早稲が膨大であっても解析される。
  • 感想
    • どこかでこの解法は見た記憶があるが、改めてなるほどーーと感じた。

秘密にするべきは暗号方式ではなく、鍵

  • 暗号化方式は秘密にしていても必ず解析されるため、秘密の暗号化方式を使うことで強化にはならない（むしろ脆弱になる）
  • したがって、秘密にするべきは鍵
  • 暗号化方式がわかっていても（いずれ解析できる）、鍵を秘密にすることで機密性を高めることができる。

第3章

XOR

  • 本筋とは関係ないが、本書で紹介されていたXORの説明が、わかりやすいかもと思ったのでメモ

    • 裏返すor裏返さないの行動を2回行った結果、オセロが最初の状態と比べて裏返されている（1）かと考えるとわかりやすい
      • 2回とも裏返す, 2回とも裏返さない → 元の面なので0
      • どちらか1回だけ裏返す → 裏返っているので1

  • A XOR B の結果を またXOR Bすると、Aに戻るというのはRubyで近しいコードが作れる

require 'set'

set = Set[1, 3, 5, 6, 7, 10]
key = Set[2, 5, 7, 10]

p set ^ key

p (set ^ key) ^ key # setと同じになる。

使い捨てパッド

  • 平文と同じ長さの完全にランダムなビット列（鍵）を用意し、XORをしたものを暗号文とするもの
  • 数学的に解読不可能であることが証明されているが、鍵の配送問題など使いづらい点が多い

AESの公募

  • NISTがAESを公募
  • プログラムが公開され、無料で使えることなどが条件
  • 応募者たちは、自分の提出したものを通すため、他の応募者の暗号方式の弱点を調べ上げることになった => 正しいコンペのかたちが実現された

第5章

RSAの由来

（本筋の話ではないが、あ、そうなの、と思ったのでメモ。）
技術的な名称の略ではなく、3人の開発者（Rivest-Shamir-Adleman）の頭文字。

RSAの暗号と複合

  • 暗号化の計算式は、暗号文 = 平文のE乗 mod N (EとNが公開鍵）
  • 複合化の計算式は、平文 = 暗号文のD乗 mod N (DとNがプライベート鍵。Nは共通）

暗号化の流れ

  • とある素数p, qをかけた数である、Nを求める
  • p-1とq-1の最小公倍数であるLを求める
  • 1より大きくLより小さい、Lとの最大公約数が1となるEを求める
  • 1より大きくLより小さい、E*D mod L = 1となるDを求める

なぜ安全？

  • 公開鍵情報に含まれるのはEだが、Eを作るために使用したp, q, Lを解読者は知らない
  • N = p * qのため、p, qが求められそう？だが、大きな数の素因数分解を高速にできる方法はまだ発見されていないので、安全と言える
    • 逆にこれが可能になったら解読可能

第6章

  • 疑似乱数発生器で生成した「セッション鍵」を対称暗号方式の鍵として、メッセージ（平文）を暗号化
  • 上記セッション鍵を公開鍵暗号方式で暗号化
  • これにより、公開鍵暗号方式の遅いというデメリットと対照暗号方式の鍵配送問題を解決している

第7章

  • 弱衝突耐性と強衝突耐性
    • 若干言葉と意味に自分的にはズレがあった
    • 弱衝突耐性
    • 強衝突耐性
      • 同じハッシュ値となる、異なる2つのメッセージを求めることが非常に困難であること

  • つまり、弱衝突耐性があれば、強衝突耐性も満たしていることになる

  • SHA-3

    • SHA-1の強衝突耐性が破られたことで新しく公募された
    • KECCAK（ケチャック）というアルゴリズムに決まった
      • そのうち、採用条件には「クリーンな構成で解析しやすいこと」というのがあった
        • 逆じゃないの？と思うかもしれないが、解析しやすい=弱点を見つけやすい→それでも弱点がないなら強いよね、ということみたい

  • 感想

    • ここまで読んでいて、Railsアプリでよく使われるdevise gemは bcryptだけど、SHA-3とかとは違うのだろうか？と思ったので少し調べた
      • bcryptはパスワードのために作られた方式で、ソルトを使った方式がデフォルトだったり、意図的に処理速度を遅くしてパスワード一覧攻撃に強くしていていることが特徴

第8章

  • 上記まででは、メッセージが正しい送信者から送られて来たものか？（認証）ができていない
  • そこで、メッセージ認証コード（MAC）という技術がある
    • 送るメッセージに対して共有鍵を使ってハッシュ化する（MAC値）
    • 送信時、メッセージと共にMAC値を送信する
    • 受信者側で、同じく持っている共有鍵を使ってMAC値を作成し、一致すれば鍵を共有している相手から来たメッセージと判断できる

第9章

  • そのメッセージを送信したのが誰か、を証明できるようにする技術が、デジタル署名
  • 公開鍵暗号方式を逆に使うことで実現している
    • 署名作成側がメッセージをハッシュ化したものを秘密鍵で暗号化
    • 検証側で公開鍵で復号し、検証

第10章

  • デジタル署名の発行元を信頼するための仕組みが、認証局
  • 認証局は、（本人確認ができている）署名作成者の公開鍵を受け取り、認証局の秘密鍵でデジタル署名したものを、作成者の公開鍵に付与した上で、受信者に送付する
  • 受信者は、認証局の公開鍵でデジタル署名を検証し、検証できたら受け取った作成者の公開鍵が正当なものであることを確認できる

おわりに

偶然なことに、この本を読んでから実務の方でもAPIの開発で暗号化や署名を付与する実装が必要になり、この本で学んだ内容が役に立ちました。 第3部は読むのに少しパワーが要りそう？で（他にやりたいこともあり）一度置いてしまいましたが、またそのうち読みたいと思います。