アルゴリズム論特論（塩田）　2020年度教材 第8回

  • 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第８回出席」とでもしてください。 $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

今日のテーマ

  • RSA暗号の設計
  • 高速べき乗アルゴリズム
　今日はRSA暗号の設計を勉強します。 公開鍵暗号のアルゴリズムは、鍵の作成と正規ユーザの通信は高速に行え、攻撃には天文学的時間が掛かるものでなければなりません。 そのポイントを押さえて聴いてください。

1. 前回の宿題

　まずは復習から。
Lemma 1（第7回 Lemma 16）　$p$ を素数とし、$p-1$ と互いに素な 2 つの自然数 $e$, $d$ が
$ed \equiv 1 \pmod{(p-1)}$
を満たすとする。このとき任意の整数 $x$ について
$x^{ed} \equiv x \pmod{p}$
が成り立つ。
　前回、誤って $x^{ed} \equiv 1 \pmod{p}$ と書いていました。 証明は正しく書いてありましたので気付いて頂ければよかったのですが、失礼いたしました。
Prop.2（第7回 Prop. 17）　Lemma 1 の状況下で次のような暗号システムが設計できる。
  • 平文集合は　 $P=\{\,0,1,\cdots,p-1\,\}$
  • 暗号文集合も $C=\{\,0,1,\cdots,p-1\,\}$
  • 暗号化関数 $E:P\rightarrow C$ は $E(x)=x^e \,\%\, p$
  • 復号関数　 $D:C\rightarrow P$ は $D(y)=y^d \,\%\, p$
  • 暗号化鍵は $(e,p)$
  • 復号鍵　は $(d,p)$
ただし、 $\%$ は Python 風に非負の最小剰余を返すとする。
宿題　$p$, $e$, $d$ をもっと巨大にしたとき、 Prop.2 の暗号は「公開鍵暗号」になるでしょうか。

2. RSA暗号の設計

　次の補題は Lemma 1 を発展させたものです。
Lemma 3　$p$, $q$ を異なる素数とし、$m$ を $p-1$ と $q-1$ の公倍数とする。 更に $m$ と互いに素な 2 つの自然数 $e$, $d$ が
$ed \equiv 1 \pmod m$
を満たすとする。このとき任意の整数 $x$ について
$x^{ed} \equiv x \pmod{pq}$
が成り立つ。
証明　$m$ は $p-1$ の倍数ですから、$ed \equiv 1 \pmod m$ から
$ed \equiv 1 \pmod{(p-1)}$
が従います（ $ed-1$ は $m$ の倍数なので $p-1$ の倍数でもあります ）。 よって Lemma 1 より
$x^{ed} \equiv x \pmod{p}$
が言えます。$q$ について同じ議論をすれば
$x^{ed} \equiv x \pmod{q}$
も成り立ちます。 すると $x^{ed}-x$ は $p$, $q$ の公倍数ですから $pq$ の倍数となります。 (証明終)
Th.4　Lemma 3 の状況下で次のような暗号システムが設計できる。 これを RSA 暗号と呼ぶ。
  • $n =pq$ とおく（ RSA modulus と呼ぶ ）。
  • 平文集合は　 $P=\{\,0,1,\cdots,n-1\,\}$
  • 暗号文集合も $C=\{\,0,1,\cdots,n-1\,\}$
  • 暗号化関数 $E:P\rightarrow C$ は $E(x)=x^e \,\%\, n$
  • 復号関数　 $D:C\rightarrow P$ は $D(y)=y^d \,\%\, n$
  • 暗号化鍵は $(e,n)$
  • 復号鍵　は $(d,n)$
ただし、 $\%$ は Python 風に非負の最小剰余を返すとする。
証明　Lemma 3 より $D(E(x)) = x^{ed} \,\%\, n = x$ となるので。(証明終)
Th.5　上の状況下、 暗号化鍵 $(e,n)$ を知っている者にとって、 以下のことは計算量的に同値である。
  1. $n$ の素因子 $p$, $q$ を知ること
  2. $p-1$ と $q-1$ の公倍数 $m$ をひとつ知ること
  3. 復号指数 $d$ を知ること
証明　(1) ⇒ (2)　$m=(p-1)(q-1)$ でも良いし、$m=\mbox{lcm}(p-1, q-1)$ でも良いし、とにかく簡単です。
(2) ⇒ (3)　宿題に同じ。
(3) ⇒ (1)　詳細は省略しますが、$d$ を用いると確率 1/2 以上で $n$ の素因子が得られる高速な計算があって、 それを繰り返しているうちに答が出ます。 (証明終)

　大きな合成数の素因数分解は困難な問題と考えられていて
Cor.6　RSA暗号は、$(e,n)$ を公開鍵、$p$, $q$, $d$ を秘密鍵とする公開鍵暗号である。
※　RSA 暗号は 1977年、Rivest, Shamir, Adleman によって提唱されました。 法に用いる素数が 1 個ではダメだったけど、2 個ならうまくいった、ということです。
RSA暗号の運用方法　
  1. Alice は $p$, $q$, $n=p\times q$, $e$, $d$ を計算し、 $(e,n)$ を公開する。
  2. Bob は Alice の公開鍵 $(e,n)$ を用いて平文を暗号化し Alice に送信する。
  3. Alice は復号鍵 $(d,n)$ を用いて暗号文を復号する。
※　RSA暗号の鍵サイズ（ = $n$, $e$ のビット長 ）はおよそ 2048 ビットが推奨されています。 この位の数になります。
p = 11830419896334923470233139452912165287787380903632581394214251606358289545144632472373008086401612166547823301528903453051277277246921194152415700551694403311225476676761024633725983594329890557790401575435742563766769460784911908958936119968228189201788490437322964527858495781642284523686054239122773001481 ( 1021 bit )
q = 2686514847608596932572805662485294864246380059778170744071295649686173875929905804514097605017443970354952041015872479315602193370998055412420469665252188699631163634703194753579484520726883128821460511910529938472602248812540517487221304834802758378189121751619516065716232830867153527161188740007838489759101 ( 1028 bit )
n = 31782598704947930047347815666308010657985089920338232341140571807015484560961238904802922881136735979885444494304830121285243370562247175373226091020631859537213084098396826264596110908163275857338794662064496950127204467031670881423037718596669229811029755658270733069577558107663085193865913908671128292466682810009257136553804394692885669223865974139912183655361316699931058911712193354180261184866494065476282846316489757918914130417542271177110570487110384228500010263659852359605005830488715831302593458453305260541164268945066932536473290694696314658727190968569372629261509374707058723115208733941910406228581 ( 2048 bit )
e = 21186635358533604637067690730900940893426144573146746124849813942032999409664994989175674940981081649066639743965714024235447209570310251304296183401288433847817909591679856385023211787571851368984342537846420049244949830958499266150756490753884290172569932258716761417222646419553278844271301342245779615466061748438116100954054011264173028081799597715475614283426073095049747946394566818506487316455876024928856794975550076232217361224440403887630332858266675005667486921875205522469099475260918869673449015029552123633162670609537189242127349753411059724043781329108915666523432289194639392460914337125899489361333
d = 21455732593208224960511614288834220088664001848253357199268398482965409193173569526651278562550226444452722313956461580826534863692513042765384823688512892211124083347853152281738490137886032200832027737223402821356460851986987787427644885402242084347523899925503136226292792892167242488771378208456000290617480813056766186186074250410075955005030549728928694296299436238465085617044439321920760656043472905850469331053667885740643296694503379404436401349719629474616920752141643650870579034219565773708668127056331133472253926654804530240164613474733472839743767100327848143298881232496532988417005244040673190075997

3. 高速べき乗

　第3回で注意したように、 宇宙の年齢がおよそ 138億年 ≒ $4.35×10^{17}$ 秒であることに比べて、 2048 ビットの整数は $10^{600}$ 以上というとてつもなく巨大な数です。 そのような数に対して RSA 暗号では $x^e\, \%\, n$ を計算しなければなりません。
  1. Python なら x ** e % n と書く式ですが、 x ** e はおよそ $2048 \times 2^{2048}$ ビットの数なので、そもそもメモリに入りません。 （ 1TiB はたった $2^{43}$ ビット ）
  2. 必要なのは $n$ で割った余りなので「 $x$ 倍して $\%\,n$ する」計算を $e$ 回繰り返せばメモリの問題は解決します。 しかし、反復回数 $e$ が巨大なので（ 計算量としては $O(n\log^2 n)$ ）、これも現実的ではありません。
　ところが、うまい手を考える人はいるもので
アイデア（反復2乗法）　$163^{91} \,\%\, 307$ で説明しましょう。
  1. べき指数 $91$ を 2 べきの和として表します。
    $91=(1011011)_2$ $\Rightarrow$ $91=64+16+8+2+1$
  2. $x^2 % 307$ を繰り返して $163^{64}\,\%\,307$ まで計算します。
    $\begin{array}{lll} 163^2\,\%\,307 &&= 167 \\ 167^2\,\%\,307 &(\ = 163^4\,\%\,307\ ) &= 259 \\ 259^2\,\%\,307 &(\ = 163^8\,\%\,307\ ) &= 155 \\ 155^2\,\%\,307 &(\ = 163^{16}\,\%\,307\ ) &= 79 \\ 79^2\,\%\,307 &(\ = 163^{32}\,\%\,307\ ) &= 101 \\ 101^2\,\%\,307 &(\ = 163^{64}\,\%\,307\ ) &= 70 \\ \end{array} $
  3. 1° , 2° を組み合わせて \begin{align} 163^{91}\,\%\,307 &= 163^{64+16+8+2+1}\,\%\,307 \\ &= (163^{64} \times 163^{16} \times 163^{8} \times 163^{2} \times 163^{1})\,\%\,307 \\ &= (70 \times 79 \times 155 \times 167 \times 163)\,\%\,307 \\ &= 2 \\ \end{align}
Th.7　$x$, $e$ が $n$ と同じくらいのビット数であれば、 反復2乗法を用いた $x^e\,\%\, n$ の計算量は $O(\log^3 n)$.
証明　1° は $e$ の2進数表示を使うだけ。 2° , 3° はいずれも、乗算と除算を最大で ( $e$ のビット長 ) 回繰り返すので、 計算量は $O(\log e) \times O(\log^2 n)=O(\log^3 n)$. (証明終)

　Python 風に書けば、こんなにも簡単です：
Algorithm 8 (反復2乗法)
  • 入力：$x$, $e$, $n$
  • 出力：$x^e\,\%\,n$
def modpow(x, e, n):
    y = 1 
    while e > 0:
        if e % 2 == 1:
            y = (y * x) % n
        x = (x * x) % n
        e //= 2
    return y
Rem.9
  • Python には反復2乗法（か、他の高速べき乗法）が組み込まれていて、 pow(x, e, n) と書けば高速に $x^e\,\%\,n$ を計算してくれます。
  • $x^e\,\%\,n$ の計算は他にも、 素数判定・素数生成の確率的アルゴリズムや、 Th.5 (3) ⇒ (1) のアルゴリズム等、 色んな所で使われます。

まとめ

  • RSA暗号の設計を学んだ。
  • RSAの暗号化関数・復号関数に必要な反復2乗法を学んだ。

自宅学習の例

  • Alg.8 を実装して Python の pow(x, e, n) と勝負してみる。

戻る