第05回 共通鍵暗号

暗号の種類

今回と次回は暗号について解説する。暗号にかかわる用語は以下の通り。 暗号には大きく分けて以下の2つがある。 共通鍵暗号ではあらかじめ鍵を共有するか、通信路を通して鍵を送らなければならないので、第三者に盗み取られる危険がある。
公開鍵暗号の2つの鍵は無関係ではないが、暗号化の鍵から復号の鍵を得るのは非常に難しい。
今回は共通鍵暗号の例をいくつか紹介する。

なお、今回も資料を紙で配布するが、課題はスマホなどからフォームを使って解くことを前提としている。この授業のページからアクセスし、文を適宜コピーして使うとよい。
課題の解答用紙はないので、どちらの課題もメールで提出する。

共通鍵暗号の例1 : シーザー暗号

概要

シーザー暗号とは、平文の文字を決められた数だけずらして暗号文を作る方法のことである。「文字を何個分ずらすか」の数値がシーザー暗号の鍵にあたる。例えばアルファベットを使う場合は、鍵に応じて下図のように文字をずらす。
受信者側でこれを復号するには、暗号文の文字を鍵の分だけ前にずらす。
(下のフォームで鍵を変更すれば文字どうしをつなぐ線が変わる。また、平文に適当な英文を入れて「↓」を押すとその下に暗号文が表示され、平文の文字を消して「↑」を押せば暗号文をもとにして平文が復元される)
平文の文字
暗号文の文字
シンボルがアルファベットの26文字なら、鍵は0~25の26パターンしかなく、そのうち0では平文と暗号文が全く同じになってしまうので、実質的に鍵は25パターンだけ。
第三者はたとえ鍵を知らなくても総当たりで試せば簡単に暗号文を解読できてしまう。

課題1

以下は上のフォームで作られた暗号文。この暗号化に使われた鍵を求めよ。
Qjmofxk, yk pqmd Imfeaz. Kagd dqrxqofuaz, ftagst bdaragzp, tmp mxdqmpk odaeeqp yk yuzp. Ngf U pmdq emk uf ymk tmhq oayq fa kagd zafuoq ftmf ur kag imxw uzfa m baef-arruoq mzp pqymzp fa eqq ftq oagzfqdraux ar mzaftqd ymz'e yqeemsq ftqdq ymk nq eayq pueuzoxuzmfuaz az ftq bmdf ar ftq arruoumxe fa anxusq kag. Ftqdq ue ea ygot dqp fmbq uz ftqeq ymffqde! Taiqhqd, U tmhq za pagnf ftmf iuft m xuffxq pqxuomok mzp ruzqeeq ftq qzp ymk nq mffmuzqp. Yqmzituxq, U etagxp xuwq uz kagd bdqeqzoq, Yd. Ahqdfaz, fa sa ftdagst ftqeq bmbqde ituot tmhq nqqz xqrf gbaz ftq fmnxq.
上のフォームでは大文字は大文字に、小文字は小文字に変換し、それ以外のものは変えないようになっている。
単純に答えが欲しいだけなら、フォームの「暗号文」のところにこの文をコピーして、一つずつ鍵の値を変えながら「↑」を押していけば「平文」のところにまともな英文が表示される。それが暗号化で使われた鍵。

共通鍵暗号の例2 : 単一(たんいつ)(かえ)()暗号

概要

単一換字暗号とは、文字を下図のような対応表に応じて置き換える方法のことである。この場合は対応表が暗号化・復号の鍵にあたる。
(シーザー暗号と同様に「↓」「↑」で暗号化・復号が行われる。「鍵を変更」を押すと表がランダムに変更される)
平文の文字
暗号文の文字


単一換字暗号のパターン数は一般に非常に多いため、シーザー暗号のように総当たりで鍵を知ることは難しい。
例えばシンボルがアルファベットの26文字なら、鍵の数はそれらの並べ替えの数、つまり \(26!=26\times25\times\cdots\times2\times1\fallingdotseq4\times10^{26}\) になる。
単一換字暗号はシーザー暗号に比べれば解読されにくいが、送信する側、受信する側の両方がこの対応表を持っている必要があるため、今回の初めに述べた脆弱性がある。
平文が十分に長い英文の場合は、以下の手がかりから解読することができる。
  • a, e, hなどは頻繁に出現し、q, zなどはめったに出てこない → 暗号文のそれぞれの文字数をカウントし、一般的な英文の出現頻度に合わせて置き換える
  • 1文字だけの単語 → 一般的な英文なら「a」か「I」しかありえない
  • 連続する2文字で頻繁に出てくる組み合わせ (th, he, in, er, ...) を手掛かりにする
例えば
Opecqyb, tb zoen Meqsuj. Buwn noxyocqauj, qfuwdf inuxuwjz, fez eynoezb cnussoz tb tajz. Gwq A zeno seb aq teb feho cuto qu buwn juqaco qfeq ax buw meyl ajqu e iusq-uxxaco ejz zotejz qu soo qfo cuwjqonxuay ux ejuqfon tej's tossedo qfono teb go suto zasajcyajeqauj uj qfo ienq ux qfo uxxacaeys qu ugyado buw. Qfono as su twcf noz qeio aj qfoso teqqons! Fumohon, A feho ju zuwgq qfeq maqf e yaqqyo zoyacecb ejz xajosso qfo ojz teb go eqqeajoz. Toejmfayo, A sfuwyz yalo aj buwn inosojco, Tn. Uhonquj, qu du qfnuwdf qfoso ieions mfacf feho gooj yoxq wiuj qfo qegyo.
のような暗号文では、大文字の「A」や小文字の「e」が一文字の単語として出てきている。これを「I」「a」だと仮定して、大文字、小文字について e→a→i→eのように置き換えれば
Opacqyb, tb zoan Maqsuj. Buwn noxyocqiuj, qfuwdf enuxuwjz, faz aynoazb cnussoz tb tijz. Gwq I zano sab iq tab faho cuto qu buwn juqico qfaq ix buw mayl ijqu a eusq-uxxico ajz zotajz qu soo qfo cuwjqonxuiy ux ajuqfon taj's tossado qfono tab go suto zisijcyijaqiuj uj qfo eanq ux qfo uxxiciays qu ugyido buw. Qfono is su twcf noz qaeo ij qfoso taqqons! Fumohon, I faho ju zuwgq qfaq miqf a yiqqyo zoyicacb ajz xijosso qfo ojz tab go aqqaijoz. Toajmfiyo, I sfuwyz yilo ij buwn enosojco, Tn. Uhonquj, qu du qfnuwdf qfoso eaeons mficf faho gooj yoxq weuj qfo qagyo.
のようになる。また、あちこちの単語の先頭に出てくる「qf」という並びが「th」(the, this, that, there などの最初の2文字)だと仮定して、qとt, fとhを置き換えれば
Opactyb, qb zoan Matsuj. Buwn noxyoctiuj, thuwdh enuxuwjz, haz aynoazb cnussoz qb qijz. Gwt I zano sab it qab hafo cuqo tu buwn jutico that ix buw mayl ijtu a eust-uxxico ajz zoqajz tu soo tho cuwjtonxuiy ux ajuthon qaj's qossado thono qab go suqo zisijcyijatiuj uj tho eant ux tho uxxiciays tu ugyido buw. Thono is su qwch noz taeo ij thoso qattons! Humofon, I hafo ju zuwgt that mith a yittyo zoyicacb ajz xijosso tho ojz qab go attaijoz. Qoajmhiyo, I shuwyz yilo ij buwn enosojco, Qn. Ufontuj, tu du thnuwdh thoso eaeons mhich hafo gooj yoxt weuj tho tagyo.
同様にして、たくさん出てくる「tho」は「the」だと仮定してoとeを置き換えれば
Epactyb, qb zean Matsuj. Buwn nexyectiuj, thuwdh onuxuwjz, haz ayneazb cnussez qb qijz. Gwt I zane sab it qab hafe cuqe tu buwn jutice that ix buw mayl ijtu a oust-uxxice ajz zeqajz tu see the cuwjtenxuiy ux ajuthen qaj's qessade thene qab ge suqe zisijcyijatiuj uj the oant ux the uxxiciays tu ugyide buw. Thene is su qwch nez taoe ij these qattens! Humefen, I hafe ju zuwgt that mith a yittye zeyicacb ajz xijesse the ejz qab ge attaijez. Qeajmhiye, I shuwyz yile ij buwn onesejce, Qn. Ufentuj, tu du thnuwdh these oaoens mhich hafe geej yext wouj the tagye.
となる。こういう手順を繰り返していけば、鍵を知らなくても平文を知ることができる。
(ちなみに、この平文は課題1の平文と同じ)

課題2

上のフォームを使って適当な英文をもとにして暗号文を作り、鍵と揃えて提出せよ。
「鍵」とは対応表だが、上側の行はa~zが順番に並んでいるだけなので、下の行のものだけがあれば十分。これと暗号文を揃えて提出する。
inserted by FC2 system