MATHGRAM

主に数学とプログラミング、時々趣味について。

Diffie-Hellman鍵共有について

以下の書籍3章前半のまとめです。

クラウドを支えるこれからの暗号技術

クラウドを支えるこれからの暗号技術

目次

  1. 公開鍵暗号
  2. Diffie-Hellman 鍵共有
  3. DLP と DHP と CDH 仮定

1. 公開鍵暗号

前回、共通鍵暗号の課題点は「秘密鍵を安全に共有できなさそう」という点でした。どれだけ安全な共通鍵暗号であろうとも秘密鍵が盗聴されてしまえば、簡単に攻撃されてしまいます。

そこで盗聴者がいたとしても、暗号を共有するものの間でのみ(複合に必要な)何らかの値を共有できるようにする手段が必要です。それを公開鍵暗号と呼び、現在では主流の暗号方式になっています。

2. Diffie-Hellman 鍵共有

「安全に」値を共有する方法の1つであるDiffie-Hellman(DH)鍵共有について解説します。

まず公開鍵暗号を考える際に念頭に置きたいのが、演算の"一方向性" です。ここでいう "一方向性" とは、Aが与えられた時にBを求めるのは計算量的にカンタンだが、逆にBを与えられた時にAを求めるのは難しい、というような性質のことを指しています。これは、例え攻撃者に盗聴されていたとしても、計算量を盾に「安全である」と決定づけるために必要となる重要な性質です。

DH鍵共有の場合は、 mod を用いた演算に潜む"一方向性" を利用することで安全な鍵共有を実現しています。

2.1. DH鍵共有のアルゴリズム

まずはDH鍵共有のアルゴリズムを見てみましょう。 ここで暗号を共有する両者を仮にAとBとし、それぞれが決めた秘密鍵 a, b とするとします。

  1. 以下の条件を満たす整数  g, p を平文で共有する。
  2.  pの条件: 1024ビット以上の整数であり、かつ \displaystyle q = (p-1)/2 素数となること
  3.  gの条件:  i, \dots , q-1に対して g^i \not\equiv 1\mod p を満たすこと
  4. Aは  K_A := g^a \mod p を求めBに共有する
  5. Bは  K_B := g^b \mod p を求めAに共有する
  6. Aは  K_B^a \mod p = g^{ba} \mod p を求める
  7. Bは  K_A^b \mod p = g^{ab} \mod p を求める

上記がDH鍵共有のアルゴリズムです。

2.2. 手計算

これだけではわかりづらいので具体的な値を入れて g^{ab} \mod p を求めてみます。 ここでは g^{ab} \mod pの値を求める部分に焦点をおくため  p の条件である、「1024ビット以上」という部分は無視するとします。

それぞれ以下のように定めます。

 p=23, g=2, a = 5, b=3

すると、以下のように  K_A K_Bを求められます。

 K_A = 2^5\mod 23 = 32 \mod 23 \equiv 9 (\mod 23)

 K_B = 2^3\mod 23 = 8 \mod 23 \equiv 8 (\mod 23)

そしてこの K_A, K_Bが共有され、AとBはそれぞれのもつ秘密鍵を用いて g^{ab} \mod pを求めます。

 K_B^a \mod p = 8^5 \mod 23 = 32768 \mod 23 \equiv 16 (\mod 23)

 K_A^b \mod p = 9^3 \mod 23 = 729 \mod 23 \equiv 16 (\mod 23)

以上の通り、 g^{ab} \mod 23 = 16 という値をAとBで共有できたことがわかります。

2.3. 軽いまとめ

公開される値は K_A, K_B, g, pの4つです。逆にAとBのそれぞれしか知り得ない秘密鍵 a, bの2つです。 鍵共有によって、AとBは  g^{ab} \mod p の値を安全に共有することができるわけですが、これは公開されている値 ( K_A, K_B, g, p) からでは  a, b を求めることが「計算量的に」難しいという前提のもと成り立っています。

その安全性を担保する仮定がCDH仮定と呼ばれるものです。

3. DLP と DHP と CDH 仮定

「計算量的に」難しい。という部分ももう少し深掘りしてみます。

DH鍵共有に対して秘密鍵を当てようとする問題を一般化してみると、以下のように表せます。

 g,p,g^a \mod p が与えられた時  a を求めよ。(それぞれの値の条件は上記と同様と する。)」

この問題を一般的に離散対数問題: DLP(Discrete Logarithm Problem) と呼ぶらしいです。

これはDH鍵共有に対して秘密鍵 a, bを求めようとした場合の問題の一般化ですが、 g, pが条件を満たす時の計算量は現実的な時間では解けません。

では、秘密鍵a,bではなく直接 g^{ab} \mod pを求めようとした場合はどうでしょうか。 この場合の問題は以下のように一般化できます。

 g,p,g^a \mod p, g^b \mod p が与えられた時  g^{ab} \mod p を求めよ。」

この問題はDHP(DH problem)と呼ばれているそうで、DLPはDHPの十分条件になります。 つまり、DLPが解けるのであればDHPも解けることになります。しかし、DHPがDLP十分条件になりうるかどうかはまだ証明されてないようです。

DHPが難しい、という仮定をCDH(Computational DH)仮定やDHA(DH Assumption)というそうです。

以上をまとめると、DH鍵共有は、CDH仮定があるからこそ安全であると言えます。

まとめ

DH鍵共有の概要をまとめました。 次回は、DH鍵共有をするために必要な大きな数字を扱うためのテクニックであるバイナリ法などをまとめます。

なんか見返してみると数学要素が少ないな....

もっと有限体の方も触れるべきだろうか🤔

と思ったけど楕円とか出てきたら大丈夫そうだからいーや。それでは。

共通鍵暗号と情報理論的安全/計算量的安全、乱択アルゴリズムについて

クラウドを支えるこれからの暗号技術を読み進めているので、自分なりに簡単にまとめようと思います。

最終的に「完全準同型暗号を実装して加乗の演算を行う」ことが目標です。

まえおき

とりあえず1章のまとめとなりますが、本書を読み進めていく上でキーワードとなりそうなものを列挙しておきます。

1 章の例としてあげられているvernam 暗号などを実装しながらポイントをまとめます。

また、これ以降、平文や暗号文は、基本的にビット列(01011100 など)として扱います。

共通鍵暗号

共通鍵暗号とは、暗号化するときと複合化するときに共通の鍵を使う暗号方式です。ここで言う鍵とは、英単語や数字、バイナリなど任意の情報を指しています。暗号を共有したい対象とこの鍵を共有するため、共通鍵暗号と呼ばれています。またこの鍵を秘密鍵と呼ぶこともあり、秘密鍵暗号と呼ばれることもあります。

以下で扱うvernam暗号も共通鍵暗号の一種です。

情報理論的安全性

暗号理論には「情報理論的安全」と言う言葉があります。

平文を \displaystyle m、暗号文を \displaystyle Enc(m)とするとき、 \displaystyle m \displaystyle Enc(m) \displaystyle n通り存在し、いずれのパターンにもなる確率が同様に確からしいとき、この暗号は情報理論的安全であると言います。

よりカンタンに書くと、

暗号文を知らない人が当てずっぽうで平文を当てる確率と、暗号文 \displaystyle Enc(m)から何らかの方法(秘密鍵を総当たりで調べるなど)で推測した時に平文を当てる確率が同じ時に、この暗号文 \displaystyle Enc(m)情報理論的安全であると言います。

適当に当てるのと同確率でしか解読ができないため、情報理論的安全が保たれていれば、平文から生成できる暗号の中でもっとも安全な暗号であると言えます。

そんな情報理論的安全性をもつ暗号として、 Vernam暗号 が有名です。

前節でも触れましたが、Vernam暗号は共通鍵暗号の一種です。

定義

サイズが \displaystyle nビットの平文 \displaystyle mに対して、 \displaystyle nビットの乱数 \displaystyle r秘密鍵とした時、


\displaystyle
Enc(m) := m \oplus r

で定められる \displaystyle Enc(m)をVernam暗号と呼ぶ。

複合化は、 \displaystyle Enc(m) \oplus r = m \oplus r \oplus rのように暗号文に対してもう一度秘密鍵排他的論理和をとれば行えます。

Vernam暗号が情報理論的安全であるのは秘密鍵 \displaystyle rが乱数で生成される部分に大きく起因しています。

実際の例を用いて、vernam暗号が情報理論的安全であること、また情報理論的安全性とはどうゆうことなのかをより具体的に確認してみましょう。

Vernam暗号

平文 \displaystyle mが4ビットの 1010 だったと仮定します。

次に平文と同サイズである4ビットの \displaystyle rを乱数で生成します。 例えばサイコロを振って奇数なら0、偶数なら1とするなどです。

この試行を行ったとして、1100となる秘密鍵 \displaystyle rが生成できたとします。

これらの \displaystyle m \displaystyle r排他的論理和をとると 0110 となりこれがVernam暗号で生成された暗号文となります。

さて、この暗号に対して攻撃を行ってみましょう。

秘密鍵がわかれば、平文を複合できるので秘密鍵を当ててみます。

平文が4ビットなので秘密鍵 \displaystyle 2^4通り存在します。またこれら全てのパターンはサイコロの目による乱数で生成されているため同様に確からしいです。

よって、正解の秘密鍵を引き当てて攻撃に成功する確率は \displaystyle 1/2^4 = 1/16 です。

これに対し、なにも考えずとにかく適当に攻撃してみましょう。

例えば、Vernam暗号のことを何も知らない通行人に、「この金庫に100万円入ってて、0と1だけで構成された4桁の数字で解錠できるんすよ。開けたら中身あげますね。」って言ったら、とりあえず全 \displaystyle 2^4通りしらみつぶしに試行しますよね、きっと。

上記の試行の結果、この金庫が解錠する可能性は当然  \displaystyle 1/2^4 =1/16 であり、この確率は「この暗号がVernam暗号だと知っていて、かつ秘密鍵を使って攻撃を行っていた人が、攻撃に成功する確率と等しい」です。

このように、暗号方式を知っていて複合化の方法も分かっている状態でも、適当に当てずっぽうで平文を解読する確率と何ら変わらないことを情報理論的安全と言っているようです。

それに対し、仮に秘密鍵のパターンが00001111の2種類しかなかったとします。この場合は、秘密鍵を用いて攻撃を行えば  \displaystyle 1/2の確率で平文を解読することが可能であり、圧倒的に当てずっぽうより確率が高いです。

このような暗号は情報理論的安全とは言えません。

vernam暗号の問題点と計算量的安全性

じゃあ、情報理論的安全なvernam暗号をみんな使えばいいじゃん。となりそうなところですが大きく2つの問題点があります。

  1. 生成した秘密鍵 \displaystyle rをどうやって共有するのか
  2. 平文と秘密鍵の情報量が変わっておらず扱いずらい

1. に関しては、結局「秘密鍵 \displaystyle rの共有するために秘密鍵を暗号化して送る必要あるんじゃない?」と言う無限ループに陥ってしまう問題ですね。つまり問題が \displaystyle mから \displaystyle rへとただ単純にすり替わっただけと捉えられます。

2. は実用的な観点です。先ほどはカンタンのために4ビットと言う小さなサイズで例としましたが実際に扱われる暗号ではもっと大きな情報量を扱います。この際、計算量などの観点からはより小さなサイズの方が実用的であり、平文と同等のサイズでしか秘密鍵を生成できないのは問題です。

ここで妥協点となるのが 計算量的安全性 です。

カンタンに言うと、「平文2048ビットに対して秘密鍵は64ビットになっちゃうけど、 \displaystyle 2^32通り全て網羅するのに、500兆年かかるからまぁ安全だよね」みたいな状態です。

厳密な定義はよく分かっていませんが、攻撃に必要な計算量を見積もり、それらが現実的に解けないと判断された暗号は計算量的安全であるといえるそうです。

vernam暗号の実装

アルゴリズムの理解を深めるためにサクッと実装したのでvernam暗号の実装とその結果を貼り付けておきます。

今仕事でTypeScriptをメインで用いているのでTSで書いていますが、ビット演算が扱いにくかったので今後の実装はGoかC++で書くと思います。

結果を貼っておきますが、特にこれは面白くないので見なくていいですw

決定的アルゴリズム乱択アルゴリズム

ここからは暗号方式に求められるアルゴリズムについてです。

まず用語の定義を整理します。

ある入力に対する出力が常に同じとなるアルゴリズムのことを決定的アルゴリズムと言います。

それに対して、ある入力に対して出力が確率的に変化するアルゴリズムのことを乱択アルゴリズム、または確率的アルゴリズムと言います。

暗号化アルゴリズムは確率的アルゴリズムであることが求められます。

平文と秘密鍵が同じならば、かならず同じ暗号文になる場合、暗号さえ盗聴できていれば平文を推測することが可能となる場合があります。

決定的アルゴリズムではない暗号方式としてCBCモードが上げられます。

CBCモードは秘密鍵と平文に加えて、IV(Initialization Vector)と言うもう1つの要素を加えて暗号化することで、同じ秘密鍵と平文を用いて暗号文を生成してもIVによって変化するというアルゴリズムです。

CBCモードの実装

CBCモードは平文をブロックに分割してそれらを逐次的に暗号化していく手法です。アルゴリズム自体は本を参照するかググってください。

以下TSによる実装と結果です。実装は特段見る必要ないのですが、同じ平文と秘密鍵でも異なる暗号文が生成できている部分に注目してください。

実行結果

1回目

IV: 8 1000
m (plain text): 3498 110110101010
r (private key): 5 0101
cbc(m) (cipher): 240 000011110000
Dec(m) (plain text): 3498 110110101010

2回目

IV: 10 1010
m (plain text): 3498 110110101010
r (private key): 5 0101
cbc(m) (cipher): 722 001011010010
Dec(m) (plain text): 3498 110110101010

このように、平文と秘密鍵が同じでもIVのおかげで異なる暗号文を生成できていることがわかります。

まとめ

  • 共通鍵暗号についてまとめました
  • 情報理論的安全性と計算量的安全性についてまとめました
  • Vernam暗号とCBCモードを解説/実装しました

【低レベルプログラミング】アセンブリ言語【その2】

前回の続きです。

本記事では、前記事で書いたハローワールドを読み解くことを目標とします。 ほとんど、低レベルプログラミングを2章までのまとめに近い内容になってるはずです。 また、付属している設問にも回答していこうと思います。

レポジトリはここです。

github.com

目次

  1. 第1章 「コンピュータアーキテクチャの基礎」のまとめ
  2. ハローワールドの解説

1. 第1章 「コンピュータアーキテクチャの基礎」のまとめ

前回は、実行環境の構築のみで各専門用語の説明を全くしていませんでした。 解説に入る前に、ちょうど第 1 章の設問が用語のまとめになりそうなので、本記事ではそこから始めようと思います。 また書籍にある、全設問を記載しているわけではないのでご注意ください。

第1章の問題と回答

  1. フォン・ノイマンアーキテクチャの主な原則は?

    1章では、フォン・ノイマンアーキテクチャの主要な機能として以下が述べられている。

    • 0 と 1 で表されるビット(bit)という情報単位のみがメモリに保存される
    • 命令とデータが区別されることなくメモリに保存される
    • メモリはラベルによってインデックスが付与された、複数の cell によって組織化されている
    • 特別な命令をのぞいて、プログラムは逐次的にフェッチされる命令軍で構成されている
  2. レジスタとは?

    CPU に直接備わっているメモリセルのこと。 レジスタにより、CPU とメモリ間のデータ交換時に生じる CPU タイムを削減できる。

  3. ハードウェアスタックとは?

    2つのマシン語命令(push と pop)と1個のレジスタrsp)によって実装された、スタックを実現するエミュレーションのこと。

  4. 割り込みとは?

    外部イベントを基準としてプログラムの実行順序を変更すること。ゼロによる除算なども割り込みによって特別なルーチンを実行する。

  5. フォン・ノイマンのモデルの主な問題点で、現在の拡張が解決しているのは?

    • メモリへの問い合わせが必須だった問題をレジスタによって解決
    • 対話性がなかった問題を割り込みによって解決
    • コードを効果的に隔離できなかった問題をハードウェアスタックにより解決
    • プログラムがどんな命令でも実行できてしまう問題をプロテクションリングによって解決
    • プログラムそのものを互いに隔離できなかった問題を仮想メモリによって解決
  6. スタックポインタの目的は?

    ハードウェアスタックのもっとも上にある要素のアドレスを格納すること。

  7. スタックは空になるか?

    ならない。push していなくても pop は実行可能であり、何らかの値を返す。

  8. スタック内の要素は数えられるか?

    不可能。7. と同じ理由で pop は任意の回数実行できる。そのため要素数を数えることはできない。

以上が、第1章の問題と回答です。 知っている人にとってはかなり当たり前の内容だと思いますが、これで一旦用語が整理できました。 それではこれらの用語を使いつつ、前記事で扱ったハローワールドを紐解いて行きましょう。

2. ハローワールドの解説

まずはハローワールドを表示するアセンブリを再掲します。

section .data
message: db 'hello, world!', 10

section .text
global _start

_start:
  mov rax, 1
  mov rdi, 1
  mov rsi, message
  mov rdx, 14
  syscall

  mov rax, 60
  xor rdi, rdi
  syscall

それでは、まずそれぞれの記述が何を意味しているのかに注目して、上から順に紐解いてみましょう。

※ 注意: この書籍で扱っているアセンブリは NASM です。GAS とは異なるので注意してください!

2.1. 文法編

2.1.1. section

まずは1行目にあるsection から。

前節で説明したように、

命令とデータが区別されることなくメモリに保存される

というのがフォン・ノイマン型の主要な機能としてあげられます。 そのため、プログラマが命令とデータを簡易的に区別できるように用いられるのがセクションです。

1行目には

section .data

と記述されていますが、section .dataグローバル変数を記述するためのセクションであることを意味します。 一方、4行目にあるsection .textは命令を記述するセクションを意味します。

セクションは機械語コンパイルされず、コンパイル時の補助的な役割を担います。 このように直接機械語に変換されず、変換処理を制御する要素をディレクティブと呼びます。

2.1.2. label

次に2行目

message: db 'hello, world!', 10

で使われている message: について。これはラベルと呼ばれます。 ラベルを用いることで、プログラマがわかりやすい名前をアドレス値に付与することができます。

高級言語の変数に似ている概念ですが、アセンブリでは変数や手続きが厳密に区別されないため、ラベルという言葉を用いるのが一般的だそうです。

参考: NASM Manual: Layout of a NASM Source Line

また、_startもラベルです。 アセンブリは複数のファイルに分けて書くことが可能ですが、どこの処理から始めるかを宣言して上げる必要があります。その時に用いられるのがこの_startラベルです。

main()関数みたいなものですかね。

2.1.3. db

同じく二行目のdbについて。これも、section と同様にディレクティブの一種です。 db ディレクティブはバイトデータを初期化するために用いられます。

つまり、以下のように記述することで、文字列hello, world!に対応する ASCII コードと、改行を示す特殊コードの10が、messsageラベルに格納されます。

message: db 'hello, world!', 10

db の他にもワードデータを初期化するためのdwやダブルワードを初期化するためのddなどが存在します。 詳しくは以下を参照してください。

参考: NASM Manual: DB and Friends: Declaring Initialized Data

2.1.4. global

次に、5 行目

global _start

にあるglobalです。 globalsectiondbと同じくディレクティブであり、プログラムの実行を開始するアドレスを指定します。 _startはラベルであり、8行目以下の命令群が格納されています。

つまりこのプログラムは_startの先頭に記述されているmov rax, 1から実行されることを意味します。

2.2. 命令編

ここまでの解説で、とりあえず各コマンドの意味は掴めてきたと思います。

次に、プログラムの主役である、命令部分を詳しく見て行きましょう。

命令部分のみを再掲します。

mov rax, 1
mov rdi, 1
mov rsi, message
mov rdx, 14
syscall

mov rax, 60
xor rdi, rdi
syscall

文法編と同様に一つずつ紐解いて行きます。

2.2.1 mov

mov とは、ある値をレジスタかメモリに書き込むために用いる命令です。 高級言語で「代入」として扱っている操作が近いです。

mov には以下のルールが存在します。

  • メモリからメモリへの移動はできない。
  • 移動元と移動先のオペランドのサイズが同じでなければならない。

mov を使って、システムコールやラベルなどが示す様々な値をレジスタに格納します。

2.2.2. syscall

syscall とは、*nix システムでシステムコールを実行するために用いる命令です。システムコールには様々な種類が存在し、一意に値が定義されています。

上のプログラムでは以下の行の1, 60システムコールを表しています。

mov rax, 1
mov rax, 60

1write60exitを意味しており、mov によって、raxレジスタに格納されています。

どちらもraxレジスタに値を格納しているのは、システムコールを実行するために以下の手順を踏む必要があるからです。

  1. rax レジスタシステムコールの番号を入れる
  2. システムコールが使用する引数は、rdi,rsi,rdx,r10,r8,r9のいずれかに格納する(これ以上の引数、つまり6個以上の引数を受け取ることはできない)
  3. syscall命令を実行する。

もう一度ハローワールドのプログラムを見てみましょう。

mov rax, 1 ; raxレジスタにwriteを格納
mov rdi, 1 ; rdiレジスタに1つ目の引数として、1を格納
mov rsi, message ; rsiに2つ目の引数として、messageを格納
mov rdx, 14 ; rdxに3目の引数として、14を格納
syscall ; syscallを実行

以上のように、システムコールを実行する手順をちゃんと踏んでいたことがわかると思います。

また、ここで linux の write システムコールのドキュメントを読んでみます。 https://linuxjm.osdn.jp/html/LDP_man-pages/man2/write.2.html

ssize_t write(int fd, const void *buf, size_t count);
write() は、 buf が指すバッファーから、ファイルディスクリプター fd が参照するファイルへ、最大 count バイトを書き込む。

このドキュメントの通りに先ほどのプログラムをみてみると、以下の操作を行なっていたことがわかります。

  • 1つ目の引数でファイルディスクリプタを指定
  • 2つ目の引数でバッファのアドレス(書き込むバイト列の先頭の値)を指定
  • 3つ目の引数で書き込むバイト数を指定

このプログラムでファイルディスクリプタ1を指定していますが、これはstdoutを示すもので「hello, world!」をターミナルに表示するための命令になります。

2.3 まとめ

それではここまで解説したことを念頭におきながらもう一度、プログラムを眺めてみます。

; .dataセクション。以下にglobal変数を定義することを宣言
section .data
; dbディレクションを用いて、
; 'hello, world!'と改行文字を示す10のバイト列を、
; messageラベルとして定義
message: db 'hello, world!', 10

; .textセクション。以下に命令を記述することを宣言
section .text
; _startラベルをgloabalディレクティブで宣言
global _start

; _startラベルとして以下の命令群を定義
_start:
  mov rax, 1 ; システムコールwriteをraxに格納
  mov rdi, 1 ; ファイルディスクリプタの値をrdiに格納
  mov rsi, message ; messageラベルの中身をrsiに格納
  mov rdx, 14 ; バイト数をrdxに格納
  syscall ; システムコールを実行

  mov rax, 60 ; システムコールexitを60に格納
  xor rdi, rdi ; 同値のxorをとってrdiの値を0に
  syscall ; システムコールを実行

うるさいくらいコメントを記述しましたが、これでわからない部分がなくなりました。

まとめ

前記事で記述したハローワールドのアセンブリを解説しました。

前回の記事で更新してなかったら死んでるとかどうの言ってましたが、生きてました。