アルゴリズム論特論（塩田）第8回 (2)　RSA暗号の設計
前へ / 戻る / 次へ $\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}}}$

補題

　次の補題は 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$ の倍数となります。 (証明終)

RSA暗号の設計

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$ となるので。(証明終)

RSA暗号の安全性の根拠

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暗号は「 素因数分解問題の困難さに基づく暗号 」と言われます。

※　RSA 暗号は 1977年、Rivest, Shamir, Adleman によって提唱されました。 宿題は法に用いる素数が 1 個だったからダメだったけど、2 個ならうまくいった、ということです。


RSA暗号の運用方法と例

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

前へ / 戻る / 次へ