ムーザルちゃんねるの「公開鍵暗号を教わってみた」を視聴する

こちらの動画を視聴して RSA 公開鍵暗号 を学びます。 大学生のころ、このあたりの授業を受けましたがすっかり忘れていますね…。

url: https://www.youtube.com/watch?v=cz1ezomeJvk
title: "公開鍵暗号を教わってみた/素因数分解が難しいからどうしたの？"
description: "#プログラミング #エンジニア #セキュリティ公開鍵・秘密鍵を雰囲気で使っている・暗号の仕組みがぜんぜんわからない・数学が苦手な人向けに、数学大好きムーさんから教えてもらいました。🛎️ 宣伝 : 本を書きました！「コードが動かないので帰れません!」新人プログラマーのためのエラーが怖くなくなる本です。エラーログの..."
host: www.youtube.com
favicon: https://www.youtube.com/s/desktop/c90d512c/img/favicon_32x32.png
image: https://i.ytimg.com/vi/cz1ezomeJvk/maxresdefault.jpg

個人的なるほどポイント

公開鍵を利用して平文を暗号化したとき、その式がシンプルだと公開鍵だけで逆算できてしまいます。 たとえば、足し算であれば引き算することで解読が可能です。

式 自体も公開情報であるため、式と公開鍵両方が第三者にわたっても復号化できないようにする必要があります。

公開指数 $e$ (encrypt) も公開鍵暗号で利用します。 $n$ について、後述する $L=(p-1)\times (q-1)$ とは異なり、 $p\times q$ であることに注意です。

$e$	公開指数	encrypt
$p$	素数	prime
$q$	素数	p の次; prime
$n$	$p\times q$ 積

暗号化の計算式は以下です。

$$c\equiv m^e(\mathrm{mod}n)$$

平文 $m$ (message?) について、公開指数 $e$ で累乗し、それを $n$ で mod を取ります。 そうして得られるものが暗号 $c$ です。

式自体はシンプルですが、 $e$ をどう定めるかはまだ説明されていません。 またどのような $p,q$ を用意すべきかについても説明されていません。 どうやって定めるのか…が数学ですね…。

累乗で mod を取ったほうが解析しづらい、というのなるほどなと思いました。 たしかに規則性が見えないですね。

公開鍵は $(e,n)$ のタプルのようです。 また秘密鍵は $d$ (decrypt) でありまだここでは説明されていません。

具体例で理解する

フローで理解していきます。 なお、注意点として $n,e,p,q,d$ の生成は Alice 側でまとめておこなわれるはずです。 図においては Bob 側で計算されているようにみえますが、 Alice 側で公開鍵と秘密鍵セットで生成し、Bob は $n,e$ の公開鍵のみ提供します。

$L$ という最小公倍数を導入します。 これは $p-1,q-1$ の最小公倍数ですが、どうして $p-1,q-1$ なのかは後述されます。

そして、 公開指数 $e$ がようやく計算されます。 $e$ は $L$ と最大公約数が 1、つまり 互いに素 な $e$ を選ぶようです。

実際の運用としては $e$ を巨大な素数とすることが多いようです。 素数であれば $L$ と互いに素になるためです（純粋な倍数でなければ）。

ここからは復号側の仕組みです。

秘密指数 $d$ は $e,L$ を利用して計算します。 公開鍵の $e$ と、$(p-1)\times (q-1)$ の $L$ を利用して計算します。

ということは Alice は $e$ と $p,q$ さえ知っていればよい、ということなのですね…。 というのも $d$ は動的に手元で計算できるためです。

下記の不定方程式を満たすような $x,y$ の組のうち、 $x$ の値が正となるものを $d$ とするようです。 いろいろな組み合わせ $x,y$ のうち、 $x>0$ を求めるようです。

$$ex+Ly=1$$

ここの計算方法については別の Qiita で勉強しようとおもいます。

暗号 $c$ を $d$ 乗し、 $n$ で mod を取ることで元の平文 $m$ が得られます。

$$m\equiv c^d(\mathrm{mod}n)$$

暗号化ステップ

1. 素数 $p,q$ を決める
   1. $p=11,q=13$
2. 積 $n=p\times q=143$ を計算する
3. $L$ を計算する
   1. $L$ は Least Common Multiple 最小公倍数
   2. $L=lcm(p-1,q-1)$
   3. $L=lcm(10,12)=60$
4. $L$ と互いに素になる (gcd = 1) $e$ を計算する
   1. $gcd(e,L)=1$ となる $e$ を計算する
   2. $e=7$ とする
      1. 別に $e=11$ でもよい
5. 暗号 $c$ を計算する
   1. $c=m^e\%n=6^7\%143=85$

復号ステップ

1. $d$ を計算する
   1. $ex+Ly=1$ かつ $x>0$ を満たすような $(x,y)$ の組を計算する
   2. このときの $x$ を $d$ とする
   3. $7x+60y=1$ を満たす $(x,y)=(43,-5)$ から、 $d=43$ とする
2. 平文 $m$ を計算する
   1. $m=e^d\%n=85^{43}\%143=6$