数のおはなしAI照合済み

暗号のしくみ

暗号の「鍵」が少ないとなぜ破られる? 鍵を2つに分けると何が変わる?
← 一覧にもどる
イメージ図(AI生成)

授業中、ケンさんの机に小さな紙切れが回ってきました。書かれていたのは「KHOOR」。英語でも日本語でもなさそうな、意味の分からない文字の並びです。差出人のユイさんは、そしらぬ顔で前を向いています。ところが、ケンさんは少し考えて、にやりと笑いました。「そうか、3つずらしか」。ふたりだけの秘密のあいさつは、どんな決まりで読めるのでしょう。そして、その決まりが二千年ほど前の手紙にも出てくるというのは、本当でしょうか。

まず予想!

「ABC」を、アルファベット順に3つ後ろへずらして書き直すと、どうなる?

「KHOOR」は、なぜ読めた?

ユイさんとケンさんのあいだには、ひとつだけ約束がありました。「アルファベットを、A→B→C→Dと、3つ後ろへずらして書く」。Hは3つ後ろでK、EはH、LはO、LはO、OはR。こうして、英語の「こんにちは」にあたる「HELLO」は、「KHOOR」になります。Zまで行ったら、Aにもどって数えます。ZOOなら、Z→C、O→R、O→Rで「CRR」です。約束を知らない人には、ただの文字の並び。約束を知っているケンさんには、ちゃんと「HELLO」と読めたのです。

この「ずらす数」のことを、暗号の世界では「鍵」と呼びます。ここでの鍵は3です。もとの文にもどすには、逆向きに、同じ数だけずらします。KHOORの文字を3つずつ前へ戻せば、HELLOに戻ります。暗号とは、鍵を知らない人には読みにくくなるように、文字を置きかえる工夫のことです。ただし、このずらし方はかんたんで、守りは弱い暗号です。鍵という言葉は、家の鍵と同じ働きだと考えると、すっと分かります。

HELLO → KHOOR(鍵3)

二千年ほど前のローマにも、同じ暗号があった?

文字をずらす暗号は、遠い昔の記録にも出てきます。ローマの歴史を書いたスエトニウスは、『ローマ皇帝伝』の中の「ユリウス・カエサル伝」に、こう書き残しています。カエサルには、キケロにあてた手紙や、親しい人への私信があり、知られたくない用件は暗号で書いた、と。そのやり方は、アルファベットの順番を動かして、どの単語も読めないようにするものでした。記録には、Aの代わりに4番目のDを書く、というように、ほかの文字も同じ決まりで置きかえる、という説明があります。

Aは1番目、Dは4番目ですから、3つ後ろにずらしているわけです。ケンさんとユイさんの約束と、同じように文字をずらす仕組みですね。この方式が「シーザー暗号」と呼ばれるのは、シーザーがカエサルの英語での呼び名だからです。文字をずらす方式は、紙と鉛筆だけで使える、いちばん素朴な暗号のひとつです。ただし、スエトニウスが書いているのは、カエサルが手紙に使ったという記録です。くわしい日付や、使われた手紙までは、ここでは確認していません。

鍵が26通りしかないと、何が困る?

アルファベットは26文字なので、ずらす数は0から25までの26通りです。0は何も変わらないので、実質25通り。さて、もし「文字をずらす方式だ」と知られてしまったら、どうなるでしょう。26通りのずらし方を全部書き出して、読める文があるか探すだけです。紙と鉛筆で、あっという間に終わってしまうほど、鍵の種類が少ないのです。これでは、とても大事な秘密は守れません。

「やり方を秘密にしておけばいいのでは?」と思うかもしれません。けれども、IPA(情報処理推進機構)は、方式そのものは公開されていて、解読を短くする欠陥が見つかっていないものが、安全な方式だと説明しています。守りの中心は、やり方の秘密ではなく、鍵のほうに置くのです。だから、鍵の種類は、ぜんぶ試せないほどたくさん必要になります。鍵の種類は「並べ方の数」で数えられます。ただし、鍵の種類が多いだけで安全になるとは限りません。下の図で、鍵を動かして、26通りの結果を見くらべてみましょう。

鍵は26通り(0を除くと25通り)
さわってみよう

まず、鍵(ずらす数)を動かして、外の円(もとの文字)と内の円(暗号の文字)の対応が変わるのを見てみましょう。つぎに「ぜんぶ試す」ボタンを押すと、鍵が26通りしかないことの意味が見えます。いちばん下のスライダーでは、2つの鍵を使う小さな例を試せます。

鍵を、どうやって相手にこっそり渡す?

シーザー暗号のように、暗号にする鍵と、もどす鍵が同じ方式を「共通鍵暗号」といいます。この方式には、大きな困りごとがあります。使う前に、同じ鍵を、相手と安全に共有しておく必要があるのです。ケンさんとユイさんは、同じ教室にいたから、こっそり約束できました。けれども、遠くにいる相手には、どうやって鍵を届ければよいのでしょう。鍵を手紙に書いて送れば、それをのぞかれたらおしまいです。

そこで、発想を変えます。暗号にする鍵と、もどす鍵を、関係のある別々の2つにするのです(1本の鍵を2つに割る、という意味ではありません)。たとえば、受け取るケンさんが、開いたままの南京錠(なんきんじょう)をたくさん配るところを想像してください。送るユイさんは、箱に物を入れて、カチャリと閉められます。けれども、開けられる鍵を持っているのは、ケンさんだけ。配ってよい暗号用の鍵を「公開鍵」、自分だけが持つもどす鍵を、この章では「ひみつの鍵」と呼びます。実際は錠前ではなく、数の計算で作ります。配られた錠前が本当にケンさんのものか、確かめる工夫も必要ですが、この章では扱いません。

この考えは、1976年にディフィとヘルマンが、論文(研究の結果を書いた文章)『暗号の新しい方向』(New Directions in Cryptography)で取り上げました。電気で遠くへ通信する場面が広がり、鍵を安全に届ける道をなるべく要らなくする、新しい種類の暗号が必要になっている、という内容です。その論文に刺激を受けた、リベスト、シャミア、エイドルマンの3人は、1977年にまとめた論文で、公開鍵でメッセージを暗号にする具体的な方法を示しました。そのはじめに、ディフィとヘルマンはこの種の暗号の考え方を示したが、その実際の方法は示していなかった、と書いています。

小さな数で、鍵のしくみをのぞいてみよう

3人が示した方法を、ごく小さな数でまねしてみましょう。使うのは「割り算の余り」です。公開する数は、33と3。33は、もどすときにも使います。ひみつにするのは、もどすための数7です。送りたい数を4とします。まず、公開の鍵で暗号にします。4を3個かけ合わせて、4×4×4で64。これを33で割ると、1あまり31です。この余りの31が、暗号です。もとの4とは、似ても似つかない数になりました。

つぎに、ひみつの鍵7で、もどします。31を7個かけ合わせると、27,512,614,111。これを33で割ると、833,715,579あまり4。ちゃんと、もとの4にもどりました。余りは、時計の針にたとえられます。13時が1時になるように、0から32までの33個の目盛りがある時計で、32の次は0にもどると考えるのです。この小さな例では、0から32までのどの数でも、公開の33と3で暗号にして、ひみつの7でもどせます。なぜもどるのかの証明は、この章では省きます。

ただし、これは仕組みを見るための練習で、守りにはなりません。33は3×11と、すぐ分けられるからです。公開の33と3を見て、ひみつの7が分かってしまう小さな例にすぎません。本物では、数をとても大きくするだけでなく、安全に使うための決まりも必要です。この章の計算を、そのまま秘密の通信に使うことはできません。また、公開鍵暗号のすべてがこの形というわけではありません。

4³=64=33×1+31

本物の鍵は、どれくらい大きな数?

ここでは、2048ビットの鍵を、大きさの例として見てみましょう(現在の推奨の長さを示すものではありません)。ビットとは、0か1を入れる箱のことです。2048個の箱に0と1を並べた数ですから、とても大きな数です。10進数に直すと、最大でも617桁です。ふだん目にするお金や人口とは、桁ちがいですね。

リベストたちの論文は、安全性の一部が、公開した数を、2つの素数(1より大きく、1と自分自身でしか割れない数)の積に分ける難しさにある、と述べています。33なら一瞬で分けられますが、数が大きくなれば、分けるのがぐんと大変になる。これが、大きな数を使う理由です。ただし、IPAは、鍵を長くすると安全性は高まる一方で、暗号にする計算ともどす計算は遅くなる、とも説明しています。安全さと速さのつり合いを、技術者はずっと考えているのです。

2048ビットの数は、617桁以下

今日、どこで使う?

IPAは、メールのような実際の使い方では、共通鍵暗号と公開鍵暗号を組み合わせることが多い、と紹介しています。手紙の本体は、速い共通鍵で暗号にします。そして、その共通鍵そのものを、公開鍵で暗号にして相手に送るのです。さっきの「鍵をどうやって渡す?」という困りごとを、公開鍵が引き受けているわけです。この章の33や7の計算は、その入口にあたる考え方だけを取り出したものです。

日本の政府機関でも、暗号の選び方は決められています。CRYPTRECが公開している「電子政府推奨暗号リスト」は、政府機関が情報システムの調達(機器やサービスを買い入れること)をするときに使われます。リストを載せたCRYPTRECのページは、文書の系列が2026年3月30日にも更新されています。暗号は一度決めたら終わりではなく、専門家が見直し続けているのです。方式と鍵の長さをどう選ぶかには、別の基準も用意されています。

あなたの身のまわりでは、まず、鍵にあたるものを大切にしましょう。パスワードは、本人だと確かめるための合言葉で、暗号の鍵とは役目がちがいます。それでも、どちらも他人に教えたり、使い回したりしないことが大切です。そして、鍵やパスワードの候補がいくつあるかは、使える文字と長さから「並べ方の数」として数えられます。その数え方は、「パスワードの強さ」の章でものぞいてみましょう。ケンさんとユイさんの紙切れ遊びは、じつは、こんな大きな世界の入口だったのです。

ひとことで言うと鍵を2つに分けると、暗号にする鍵は配ってよくなる。

使ってみよう

鍵3のシーザー暗号で、「CAT」を暗号にすると?
Cは3つ後ろでF
Aは3つ後ろでD
Tは3つ後ろでW
答え:FDW
鍵4のシーザー暗号の暗号文「XLIVI」を、もとにもどすと?
もどすときは4つ前へずらす
X→T、L→H、I→E、V→R、I→E
答え:THERE
本文の小さな例(公開:33と3)で、送りたい数が5のとき、暗号はいくつ?
5を3回かける:5×5×5 = 125
125 ÷ 33 = 3あまり26(33×3 = 99、125 − 99 = 26)
答え:26(ひみつの鍵7で、26⁷ ÷ 33の余りを求めると5にもどります)

よくある「あれ?」

暗号のやり方を秘密にしておけば、安全 → 方式は知られていても、鍵が見つからなければ守れる。ただし鍵の種類が少なければ、やり方が秘密でも全部試される
やり方が分からなければ手が出ないように思えるからです。でもシーザー暗号は、やり方を知らなくても、26通りくらいなら試せてしまいます。IPAは、公開されていて解読を短縮する欠陥が見つかっていない方式が安全だと説明しています。
公開する鍵があるなら、ひみつの鍵もすぐ分かる → この章の33のような小さな数ならすぐ分かってしまう。そこで実際には、とても大きな数を使う方式がある
本文の例では、33が3×11だと気づくと、ひみつの7が作れるからです。だから実際には、とても大きな数を使います。

これ、どこで使う?

メールのように、実際の使い方では、共通鍵暗号と公開鍵暗号を組み合わせることが多いと、IPAは紹介しています。メッセージ本体は速い共通鍵で暗号にして、その共通鍵を公開鍵で暗号にして送る方法です。この章は、その入口にあたる考え方だけを扱っています。

なるほど2問

ほんとうは…・出典

「ひみつの鍵」という呼び方

この章では、公開鍵暗号でもどすための鍵を「ひみつの鍵」と呼びました。IPAのQ&Aでは、「秘密鍵」の語は共通鍵暗号の別名として出てくるため、混乱しないよう、公開鍵暗号の側は「ひみつの鍵」と書いています。他の資料で別の呼び方をしているかどうかは、今回確認していません(未確認)。

「大きな数の素因数分解が難しい」ことの扱い

この章では、小さな練習例のあとで、実際には大きな数を使う方式がある、とだけ紹介しました。「素因数分解が速くできる方法はない」と言い切れるかどうかを直接述べた公的資料は、今回確認していません(未確認)。そのため本文では、そう断定していません。また、公開鍵暗号のすべてが素因数分解にもとづく、という意味でもありません。

総務省・NICTの資料は未確認

総務省とNICTの暗号に関する解説ページを探しましたが、今回は本章の内容を直接確認できるものに行き当たりませんでした(未確認)。そのため出典に載せていません。

この章が省いていること

33と3と7の例が、なぜ0〜32のどの数でももとにもどるかの証明(割り算の余りの性質)は省きました。とても大きな数での計算のしかたや、実際の通信での使われ方、量子計算機の影響も扱っていません。文字の置きかえを26通りより増やした暗号が、それでも読まれてしまう理由も扱っていません。実在のサービスの暗号を破る方法は、書いていません。

2048ビットと桁数

2048ビットの数は、2²⁰⁴⁷ 以上 2²⁰⁴⁸ 未満で、10進数ではどれも617桁です。そこで「10進数で最大でも617桁」としました。IPAが挙げる「2048ビットまで」は、アーカイブのQ&Aにある鍵の長さの目安で、現在の推奨長を示すものではありません。推奨される鍵長はCRYPTRECの設定基準(LS-0003-2022R1)を見る必要があります(その本文は今回確認していません)。

カエサルの暗号は確認、名前の由来は未確認

スエトニウス『ローマ皇帝伝』「ユリウス・カエサル伝」第56章に、カエサルが手紙でAの代わりにDを書くような暗号を使ったという記述があることは、シカゴ大学のサイト(LacusCurtius)で確認しました。ただし、いつ、どの手紙で使われたかは確認していません。また、この暗号が「シーザー暗号」と呼ばれるようになった経緯は、公的資料で確認できていません(未確認)。本文は「カエサルの英語での呼び名だから」とだけ書いています。この暗号を最初に考えた人も分かっていません。

RSA論文と、ディフィ・ヘルマン論文の年

ディフィとヘルマンの論文は1976年11月のIEEE Transactions on Information Theory(第IT-22巻6号、644〜654ページ)で、スタンフォード大学のヘルマンのページにある原文で確認しました。リベストらの論文は、MIT側の原稿に「1977年4月4日受理、同年9月1日改訂」とあるので、本文は「1977年にまとまった論文」としました。学術誌に載った年は公的資料では確認していません(未確認)。「RSA」の名の由来は確認していません(未確認)。

出典と確認状態(AI照合済み)

例題・数値はこのサイトのオリジナルです(実在の店・商品とは関係ありません)。

この章で、まちがいや古くなった情報に気づいたら、報告フォームから教えてください