第 11 回暗号理論

本日の内容

11-1. アイスブレイク
11-2. レポート課題
11-3. 講義

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

11-1. アイスブレイク

本日の属性

謎解きが好き		整数の問題が好き
学籍番号	氏名	(番号欄)
語学が好き		寒くなって体調を崩した

11-2. レポート課題

ワーク11-1

次の暗号を解きなさい

Avrfv Klurp Bupclyzpaf (AKB) dhz mvbuklk pu 1907 if adv fvbun lunpullyz dov wshflk hjapcl yvslz pu aol pukbzayphs dvysk, Zlppjop Opyvah huk Zopurpjop Vnptvav, av jvujylapgl aolpy zbisptl pklh, “Wyvtvapun lunpullypun lkbjhapvu pz pukllk aol mvbukhapvu mvy aol klclsvwtlua vm h uhapvu.”

ヒント

シーザー暗号解読機を用いると簡単

ワーク11-2

グループ内でシーザー暗号文をやり取りし、鍵無しで解けるか確認しなさい

ワーク11-3

RSA 暗号鍵作成シートを用いて RSA暗号を作りなさい。また、べき乗電卓を用いて、暗号の確認をしなさい

ワーク11-4

次の暗号を解きなさい

Hudxu Zyldg Klgpybvghx (HZK) nsv iuklzyz gl 1907 ex hnu xuklo yloglyybv nau cmsxyz srhgpy bumyv gl hay glzkvhbgsm nubmz, Vyggrag Agbuhs slz Vagldgrag Uogquhu, hu rulrbyhgjy haygb vkemgqy gzys, “Cbuquhglo yloglyybglo yzkrshgul gv glzyyz hay iuklzshgul iub hay zypymucqylh ui s lshgul.” Habukoa ghv vumgz slz zgmgoylh srszyqgr rkmhkby, HZK asv eyyl iuvhybglo vhkzylhv iub quby hasl s rylhkbx ngha hay qgvvgul, “Zypymucqylh ui Akqsl Byvukbryv Nau Rulhbgekhy hu Vurgyhx ex Hyralumuox.” HZK smvu asv eyyl cbupgzglo fksmghx glvhbkrhgul esvyz ul hay hnu yzkrshgulsm qswgqv: “Byvcyrh iub Cbsrhgrsm Vhkzx” slz “Vhkzylhv Igbvh.” HZK rulhglkyv hu rkmhgpshy ywrymmylh akqsl byvukbryv hu qyyh hay lyyzv ui vurgyhx, rasloglo ngha hay hgqyv hu qsdy vgolgigrslh rulhbgekhgulv hu hay zypymucqylh ui Tscsl’v vrgylry slz hyralumuox.

ヒント

単一換字式暗号解読機を用いる

締切、提出方法

来週の火曜日の夕方までに <[email protected]>宛に一通のレポートを作成し、メールすること。

暗号とは、送りたい情報(平文)を別の情報(暗号文) に置き換え、送りたい情報そのものを秘匿する技術です。但し、鍵を持っていると、暗号文から元の平文を求める (復号)できることが必要です。平文 $p$ から暗号文 $c$ を作る操作を暗号化と言いますが、これは一般には鍵 $k$ に対する暗号関数 $e_{k} (\cdot)$ と復号関数 $d_{k} (\cdot)$ により次の関係を示すことができます。

c = e_{k} (p)

p = d_{k} (c)

$d_{k}$ は必ず存在しなければならないので、鍵の全探索 (ブルートフォースアタック) により、暗号は必ず解くことができます。但し、鍵の全体集合(鍵空間)が十分に大きければ、ブルートフォースアタックに対して、解かれにくくなります。暗号への攻撃はブルートフォースアタックのみではありませんが、様々な攻撃への耐性のことを強度と言います。鍵空間の大きい暗号は、ブルートフォースアタックに対して強度を持つことになります。

暗号の種類

ブロック暗号、ストリーム暗号: ブロック暗号は、平文の一定の長さの文字列を別の文字列に置き換える暗号方式。ブロックごとに同じ暗号を用います。ストリーム暗号はビットごと、あるいはバイトごとに別のビット、バイトに置き換えるが、位置ごとに異なる暗号化を用いることで、強度を上げます。
標準暗号: 暗号は日常的に必要な技術です。そのため、扱いやすく強度の強い暗号が求められています。アメリカでは、以前は国家暗号規格として DES 暗号が定められていましたが、安全性に問題が生じたため、アメリカ国立標準技術研究所（NIST）が主導して新たに定められたのがAES 暗号です。無線LANのパスワード保護など、様々な場面で使用されています。

暗号の利用

インターネットを使用していると様々な暗号技術を使用します。

TLS(Transport Layer Security): TCP の通信を暗号化する技術です。公開した鍵に関してもなりすましを防ぐため、証明書や、証明局を定めています。
HTTPS: TLS を用いたWebの通信です。ブラウザで使用する場合、相手方の信頼性を示すために、アドレス欄に鍵のマークが表示されたり、色が変わったりします。
Wi-Fi Protected Access: WPA2は現行の無線LANの暗号化方式。AESを採用している。なお、WPA3が登場し、2018年後半より順次リリース予定
ssh(Secure Shell): 遠隔ホストにアクセスするためのプロトコル。ネットワーク技術者には基本的な接続方法

単純な暗号

シーザー暗号

文字に順番がある時、文字列を暗号化するときに、それぞれの文字の順番をずらすのをシーザー暗号と言います。

IBM → HAL

これは鍵空間が狭いので、ブルートフォースアタックで簡単に解けます。

単一換字式暗号

文字を入れ替えて作る暗号を単一換字式暗号と言います。鍵空間は広いのですが、元の平文の性質をそのまま持つため、英語だと「eが多い」「一文字の単語は a, I」「the, are, with などよく出てくる単語にパターンがある」などのテクニックで解けます。

したがって、ブロック暗号を作る場合は、ある程度ブロック長を長く取る必要があります。

現代暗号に必要な数学的な基礎

ユークリッドの互除法と、拡張ユークリッド互除法

２つの正の整数に対して、大きい方を小さい方で割った余りを求め、小さい方とその余りについても割り算を繰り返していくことにより、最終的に割り切れる直前の余りが与えられた２数の最大公約数になるというのがユークリッドの互除法です。与えられた正の整数を $a, b$ とします $(a > b)$ 。この時、各商を $q_{i}$ , 、各余りを $r_{i}$ と表すと、次のように書くことができます。

a = q_{0} b + r_{0}

b = q_{1} r_{0} + r_{1}

r_{0} = q_{2} r_{1} + r_{2}

⋮

r_{k - 2} = q_{k} r_{k - 1} + r_{k}

r_{k - 1} = q_{k + 1} r_{k}

(r_{0} ... r_{k} \neq 0)

\gcd = r_{k}

さて、この割り算の式の列について、 $\gcd = r_{k}$ が求まっている時、その式を利用すると、その上の $r_{k - 2}$ と $r_{k - 3}$ の式に対して、 $r_{k - 1}$ と gcd の式を代入することで、 $r_{k - 2}$ とgcd の式を求めることができる。

r_{k - 3} = q_{k - 1} r_{k - 2} + r_{k - 1}

r_{k - 2} = q_{k} r_{k - 1} + r_{k}

\to

q_{k} r_{k - 3} = (q_{k} q_{k - 1} + 1) r_{k - 2} - r_{k}

これを繰り返すと、 $(r_{i - 2}, r_{i - 1}, r_{k})$ に $(r_{i - 1}, r_{i}, \gcd)$ の式を使って、 $(r_{i - 2}, r_{i - 1}, \gcd)$ の式を得ることができる。したがって、最終的に $(a, b, \gcd)$ からなる式 $X a + Y b = \gcd$ を得ることできます。これを拡張ユークリッド互除法と言います。

なお、この等式は一通りではなく何通りも求めることができます。特に、正の $X$ を求めたいのに、負の値が求まってしまった場合、 $b a - a b = 0$ は常に成り立つので、各項を対応して足し引きすれば良いです。

フェルマーの小定理

数 $n$ に対する合同式とは次のような式を言います。

A \equiv B (mod n)

これは $A - B$ が $n$ で割り切れることを意味します。

フェルマーの小定理とは素数 $p$ とそれに素な整数 $x$ に対して次が成り立ちます。

x^{p} \equiv x (mod p)

オイラー関数

数とその素因数分解が以下のとおりとします。

n = {p_{1}}^{e_{1}} ... {p_{k}}^{e_{k}}

この時オイラー関数は以下のように定義されます。

φ (n) = n (1 - \frac{1}{p_{1}}) ... (1 - \frac{1}{p_{k}})

$n$ と互いに素な整数 $x$ には次の性質があります。

x^{φ (n)} \equiv 1 (mod n)

公開鍵暗号

古くから使われている暗号は、暗号化の手法から復号の手法がすぐにわかるようなものです。このような暗号を共通鍵暗号と言います。一方、暗号化鍵を知っても復号化が直ちにできないような暗号は、暗号化鍵を公開しても安全性が保たれます。これを、公開鍵暗号と言います。古典暗号理論では鍵は秘匿しながら受信者と共有しなければなりませんでしたが、その共有するのに、どのような通信を行えばよいかという鍵配布問題は未解決問題でした。

ところが、Diffie と Hellmanは暗号鍵から復号鍵が求めにくいような暗号システムを提案しました(1976)。このシステムでは受信者が暗号鍵を盗聴可能な通信路で送信者に送れば、平文は盗聴されずに通信が行なえます。このようなシステムを公開鍵暗号システムと言います。公開鍵暗号は根本的に鍵配布問題を解決します。

RSA暗号

Rivest, Shamir, Adleman が開発した公開鍵暗号方式（1977）。

2つの素数 p, q の積に対するオイラー関数は次で得られます。

φ (p q) = p q (1 - \frac{1}{p}) (1 - \frac{1}{q}) = (p - 1) (q - 1)

ここで、以下の条件を持つ、ある２つの数 e,d を求めます。

e d \equiv 1 (mod φ (p q))

すると、p,q と互いに素な数 x に対して次が成り立ちます。

x^{e d} \equiv x (mod p q)

ここで、e,n=pq から d を求めるのは、 p,q を知っていれば容易ですが、そうでなければ有効なアルゴリズムは知られていません。そこで、暗号化鍵、復号化鍵を次のように定めると、公開鍵暗号であるRSA 鍵を作ることができます。

encrypto (x) = x^{e} (mod p q)

decrypto (y) = y^{d} (mod p q)

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 11 回 暗号理論