こんにちは、nodaです。
最近、WEB+DB PRESS plusシリーズの『～を支える技術』をお気に入りで読んでいます。
(コーディングを支える技術とか、Googleを支える技術とか…)
それに触発されてか、タイトルを似せてしまいました…
暗号をテーマに歴史的なところを書きますが、最後までお付き合い頂ければ幸いです。
さて、Symantecの報告「Android の暗号化に関する問題が数十万ものアプリに影響する恐れ」において、Androidの乱数生成機能の脆弱性が36万以上のアプリにある可能性を示し、注意を喚起しています。
この報告によると、SecureRandomクラスと呼ばれる乱数生成クラスに問題があり、生成された乱数が簡単に推測されたり同じ乱数が使われる可能性があるとのことです。
つまり、SecureRandomクラスで生成された乱数を”暗号文(暗号化した後のメッセージ ⇔ 平文)”として使用するアプリは、暗号による安全性が欠けており、危険であるといえます。
※Android Ver.4.2(Jelly Bean)以降は、SecureRandomクラスが再実装されたため、この固有の欠陥の影響を受けないとされています。
現代においても暗号の技術は完璧ではなく、前述のような脆弱性をついて暗号解読されたり、ブルートフォースアタックのような力づくの攻撃で破られる暗号もあります。
『絶対に解読されない暗号アルゴリズムは存在しない』（出典：暗号技術入門 結城浩）とあるように、すべての鍵をしらみつぶしに試すことで、どんな暗号もいつかは解読されてしまいます。
そしてその歴史は古く、暗号の歴史は、”暗号化する側”と”解読する側”(悪意をもって平文に復元しようとする人の意味です。正当な手順で平文を入手することは”復号化(復号)”と呼びます。)の「いたちごっこ」であり、今もなお繰り広げられています。
それではその「いたちごっこ」はいつ頃から始まったのでしょうか。
『暗号解読』[サイモン・シン]によれば、古くは紀元前5世紀の”秘密の書記法”まで遡ります。
暗号の誕生!?～秘密の書記法～
紀元前5世紀の歴史的な背景から述べます。
当時、ペルシャの専制君主クセルクセスはギリシャ征服に向け軍備増強をしていました。
一方でギリシャへの忠義心をもった元スパルタ王のデマラトゥスは、クセルクセスの侵略計画を知らせる文章をスパルタの人々に送ることにします。
しかし、ペルシャの衛兵に見つからずに文章を送るにはどうしたものかと、デマラトゥスは一計を案じることになります。
その一計とは次のようなものになります。
『二枚一組になった折りたたみ式の書字板を入手すると、その表面のロウ(ワックスのこと)を削り取り、書字板の木の部分に王の計画を書き写し、文字の上にロウを塗り直して、国道警備の者に見咎められても事なきを得るようにした。』
（出典：暗号解読 サイモン・シン）
かくして、書字板が無事スパルタに届き、書字版の秘密に気づいたスパルタ人は警告を受け取ることができました。
今回、デマラトゥスがとった秘密通信は、単にメッセージを隠すというものでした。
このようにメッセージの存在を隠すタイプの秘密通信のことを”ステガノグラフィ(steganography)”といいます。
これ以降にも、さまざまなステガノグラフィが利用されてきましたが、ステガノグラフィには根本的な欠陥があるとされています。
それはメッセージの露見が、そのまま秘密の漏洩につながってしまうことです。
※ちなみに、最近でもステガノグラフィは“電子透かし”という技術に使われています。
ステガノグラフィに対して、よく知られている暗号(メッセージの内容を読めないようにすること)のことを”クリプトグラフィ(cryptography)”といいます。
この後の歴史では、ステガノグラフィの安全性が保証されなくなったことにより、それを補うように暗号(クリプトグラフィ)が発展することとなります。
またステガノグラフィの欠陥を補うために、暗号(クリプトグラフィ)とステガノグラフィを組み合わせる技術がよく使われています。
『暗号(クリプトグラフィ)は内容を隠し、ステガノグラフィは存在を隠します。そして暗号とステガノグラフィを組み合わせれば、2つの技法を組み合わせた効果を生むことができるとされています。』
（出典：暗号技術入門 結城浩）
歴史上の暗号(クリプトグラフィ)
ここからは歴史上に登場した有名な暗号(クリプトグラフィ)を挙げていきます。
シーザー暗号
“シーザー暗号”は紀元前1世紀ごろの古代ローマで、武将ジュリアス・シーザーが使っていたといわれる暗号です。
単純な暗号であり、平文で使われている文字(例えばアルファベットなど)を”ずらす(シフト)”することによって暗号化を行います。
本当に単純ですが、アルファベットの平文を暗号化した例です。
出典：『Wikipedia』[シーザー暗号]
fig.1ではアルファベットを3文字ずらしています。
“NODA”という平文を暗号化すると、”QRGD”となります。
次に復号化です。
復号化するための鍵はアルファベットをずらした文字数の”3″となり、暗号化の時と逆方向にずらせば復号化となります。
シーザー暗号は単純なだけに、ブルートフォースアタックで簡単に解読されてしまいます。
今回はアルファベット(26文字)を何文字ずらすかが鍵となっていたので、全くずらさないケースを含めても鍵は26通りしかありません。
つまり、26回の攻撃で暗号解読されてしまうので、シーザー暗号は重要な秘密を守るには弱すぎるといえます。
単一換字暗号
シーザー暗号での例のように、アルファベット26文字が一対一の対応関係で成り立っていれば、どんな対応関係でも暗号が作れます。
このように平文を構成する文字を、別の文字へ変換する暗号のことを”単一換字暗号”といいます。
※ずらす文字数が固定されているシーザー暗号も、単一換字式暗号の一種であるといえます。
アルファベットを使用した例です。
fig.2の通りに再度、”NODA”という平文を暗号化すると、今回は”WGAI”となります。
次に復号化ですが、鍵となるのはfig.2のような”換字表”です。
換字表をもって、暗号化時と逆に変換することで復号化となります。
今回の単一換字暗号は、シーザー暗号に比べてはるかに多くの鍵の候補があるため、ブルートフォースアタックでの解読は困難となります。
アルファベットの例では、考えられる鍵の総数は”403291461126605635584000000″となります。
ブルートフォースアタックで1秒間に10億個の鍵を調べたとしても、すべての鍵を試すのに120億年以上の時間がかかります。
単一換字暗号において、ブルートフォースアタックでの暗号解読は不可能といえますが、”頻度分析”と呼ばれる暗号解読法で解読することができます。
頻度分析
頻度分析は例を挙げるとわかりやすいので、暗号文の解読を実際に行ってみます。
次の暗号文を入手し、平文は英語で書かれ、単一換字暗号で暗号化されたと想定します。
SYZMPGWOKXIATDZYRZYPZGLIWAPGDAFDMCGDWSIKKYMINNZMG
CEYCJSEYMEYPMEYDPINNKDCIMDGWZIPYILLYCMYAIWAMGLGKK
GSMEYZMYNZGRMKDWYAFXFDMCGDWGPOMGUIJYMEYDPLRWAZZIL
YSYSGRKAIKZGKDJYMGIATDZYIWAPGDAAYTYKGNYPZMGZMIXMR
WYAIWAPYTDYSMEYDPCPXNMGOPINEDCDUNKYUYWMIMDGWZFIZY
AGWZYCRPYPIWAGUIWAYTIKRIMYSEYMEYPMEDZCGRKANGZYIZY
CRPDMXPDZJ
この暗号文に使用されている文字の頻度は次の表になります。
続いて解読の手がかりとして、新聞や小説などからサンプリングしたアルファベットの出現頻度を使用します。
下の表は『暗号解読』[サイモン・シン]に記載されていた出現頻度表になります。
どうやら英語の文章で使われる文字で、最も出現頻度が高いのは”e”のようです。
従って暗号文の”Y”は、平文に変換すると”e”であると仮定することができます。
“Y”→”e”に変換したものが次です。
SeZMPGWOKXIATDZeRZePZGLIWAPGDAFDMCGDWSIKKeMINNZMG
CEeCJSEeMEePMEeDPINNKDCIMDGWZIPeILLeCMeAIWAMGLGKK
GSMEeZMeNZGRMKDWeAFXFDMCGDWGPOMGUIJeMEeDPLRWAZZIL
eSeSGRKAIKZGKDJeMGIATDZeIWAPGDAAeTeKGNePZMGZMIXMR
WeAIWAPeTDeSMEeDPCPXNMGOPINEDCDUNKeUeWMIMDGWZFIZe
AGWZeCRPePIWAGUIWAeTIKRIMeSEeMEePMEDZCGRKANGZeIZe
CRPDMXPDZJ
英語で最もよく使用される単語は”the”です。
そこで、”e”で終わる3文字のパターンを検索すると、”MEe”という組み合わせが6回も登場しますので、”MEe”が”the”である可能性が高そうです。
“M”→”t”、”E”→”h”に変換したものが次です。
SeZtPGWOKXIATDZeRZePZGLIWAPGDAFDtCGDWSIKKetINNZtG
CheCJShethePtheDPINNKDCItDGWZIPeILLeCteAIWAtGLGKK
GStheZteNZGRtKDWeAFXFDtCGDWGPOtGUIJetheDPLRWAZZIL
eSeSGRKAIKZGKDJetGIATDZeIWAPGDAAeTeKGNePZtGZtIXtR
WeAIWAPeTDeStheDPCPXNtGOPINhDCDUNKeUeWtItDGWZFIZe
AGWZeCRPePIWAGUIWAeTIKRIteShethePthDZCGRKANGZeIZe
CRPDtXPDZJ
次に英語の出現頻度として高いのは”a”、”o”、”i”ですが、そのまま”G”、”I”、”D”の順に当てはめるのは強引です。
(暗号文での出現回数にひらきがないためです。)
しかし、”G”が”o”であると仮定すると、”to”という単語が5回も登場します。
この要領で、英単語の知識をフルに活用して解読を続けます。
“hethe”が2回でてきて、前後の文字が”ShetheP”が共通して登場します。
これを”whether”と仮定すると、”S”が”w”、”P”が”r”となります。
“G”→”o”、”S”→”w”、”P”→”r”に変換したものが次です。
weZtroWOKXIATDZeRZerZoLIWAroDAFDtCoDWwIKKetINNZto
CheCJwhethertheDrINNKDCItDoWZIreILLeCteAIWAtoLoKK
owtheZteNZoRtKDWeAFXFDtCoDWorOtoUIJetheDrLRWAZZIL
ewewoRKAIKZoKDJetoIATDZeIWAroDAAeTeKoNerZtoZtIXtR
WeAIWAreTDewtheDrCrXNtoOrINhDCDUNKeUeWtItDoWZFIZe
AoWZeCRrerIWAoUIWAeTIKRItewhetherthDZCoRKANoZeIZe
CRrDtXrDZJ
この調子で試行錯誤をしながら解読を続けると、次の換字表が出来上がります。
換字表の通りに変換すると次のような平文になります。
westronglyadviseusersofandroidbitcoinwalletappsto
checkwhethertheirapplicationsareaffectedandtofoll
owthestepsoutlinedbybitcoinorgtomaketheirfundssaf
ewewouldalsoliketoadviseandroiddeveloperstostaytu
nedandreviewtheircryptographicimplementationsbase
donsecurerandomandevaluatewhetherthiscouldposease
curityrisk
これにスペースや記号を入れて、読みやすくします。
We strongly advise users of Android bitcoin wallet apps to check whether their applications are affected and tofollow the steps outlined by bitcoin.org to make their funds safe. We would also like to advise Android developers
to stay tuned and review their cryptographic implementations based on SecureRandom and evaluate whether this
could pose a security risk.
冒頭で紹介したSymantec報告の英文になりました。
解読作業は如何でしたでしょうか？
多くの場面で”仮定”という作業が発生し、実際には手戻りなどがあると思います。
しかし根気よく作業を続ければ、単一換字暗号であっても暗号解読が可能となります。
頻度分析の解読作業で次のようなことがわかるとされています。
- 頻度の高い文字だけでなく、低い文字も手がかりになる。
- はじめと終わりがわかると手がかりになる。単語の区切りがわかれば、それも手がかりとなる。
- 暗号文が長いと解読しやすくなる。
- 同じ文字の連続は手がかりになる。
- 解読のスピードはだんだん上がっていく。
（出典：暗号技術入門 結城浩）
単一換字暗号は紀元前から何百年も使われてきましたが、アラビアの学者によって頻度分析が生み出され、解読されるようになります。
シーザー暗号や単一換字暗号は、現代では使われることはありません。(これから紹介するエニグマ暗号も同様です。)
しかし暗号の基礎となるアルゴリズムと鍵の関係などは、暗号技術の発展に欠かせませんでした。
現代ではインターネット商取引で使用されるなど、暗号は民間活動に大きな影響を及ぼしています。
しかし、その発展には軍事上の必要性・重要性が高かったことが大きいようです。
代表例として”エニグマ”を取り上げます。
エニグマ
エニグマとは、第二次世界大戦中にドイツで使用された暗号機械です。
もともと商用として発明されたエニグマは、ナチスドイツ時代のドイツ国防軍に採用され、軍用として使用されました。
出典：『Wikipedia』[エニグマ (暗号機)]
エニグマはタイプライターのような機械で、暗号化と復号化を1台で行うことができます。
簡単ですがエニグマによる暗号通信の流れは以下です。
- 送信者はエニグマを使って平文を暗号化し、暗号文を無線で送ります。
- 受信者は暗号文をエニグマで復号化し、平文を得ることになります。
送信者と受信者には予め”国防軍鍵表”という厚い冊子が配られます。
国防軍鍵表には”日替わり鍵”が記されており、送信者と受信者は日替わり鍵の通りにエニグマを設定します。
エニグマの詳しい構造や暗号・復号化はとても複雑です。
戦争にも使われたので当たり前ですが…
Wikipediaなどでも図解で説明されていますので、興味のある方はコチラを参照して下さい。
まとめ
さて、暗号の歴史を第二次世界大戦まで遡ったところで、いよいよ暗号はコンピュータで処理される時代となります。
(歴史的な話をするだけで意外と長くなってしまいました…)
近現代になると“対称暗号(共通鍵暗号)”がもつ”鍵配送問題”への解決策として、“公開鍵暗号”が発明されます。
また、対称暗号と公開鍵暗号の長所を組み合わせた”ハイブリッド暗号システム”が可能となりました。
これらを支える技術は、計算方法(暗号アルゴリズム)であったり、認証に必要な“一方向ハッシュ関数”など面白そうな話題がまだまだあります。
さらに近未来の話題ですと、冒頭で『どんな暗号もいつかは解読される』としましたが、完全な暗号技術になると期待されているのが“量子暗号”です。
しかし、どんなに完全な暗号技術だったとしても、それを使用する”人”が重要な鍵を握っていると思います。
今回、本記事を書くにあたっての調査をしていると、歴史上の人物“スコットランド女王メアリー”が暗号についての教訓を残していることに気付きました。
彼女はエリザベス女王の暗殺を企てた罪として処刑されたわけですが、その計画が暴かれたのは暗号に対する意識の低さからでした。
暗殺計画を暗号化したことで安心した彼女は、その暗号は誰にも破られないと過信し、共犯者たちと手紙で暗殺を企てていたのです。
以上のことから、暗号技術に過信せず、支えられている技術を正しく理解しなければならないと考えます。
そして、これらの技術に触れるすべての人は、メアリーのように機密性の高い情報はぞんざいに扱わず、正しいセキュリティ意識を持たなければなりません。
最後まで読んでいただき、ありがとうございます。
暗号について少しでも興味をもっていただけたら幸いです。
ではでは。
参考文献
- 結城浩. (2013) 新版 暗号技術入門-秘密の国のアリス. ソフトバンク クリエイティブ. 東京
- サイモン・シン. (2007) 暗号解読(上) 新潮社. 東京
- Symantec. Android の暗号化に関する問題が数十万ものアプリに影響する恐れ. http://www.symantec.com/connect/ja/blogs/android-20 (2013年9月15日アクセス)
