Pebble Coding

プログラマーの作業メモ

RSA暗号化方式を紐解く その(2)

前回からの続きです。
暗号化は
c = {m} ^ {e} \mod n の式によって行い、
復号化は
m = {c} ^ {d} \mod n の式によって行います。
これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。
理論の根幹をなす定理がフェルマーの小定理を一般の整数に拡張したオイラーの定理です。

オイラーの定理
a>0, n>0 を互いに素な整数とした時、 {a} ^ { \phi (n) } = 1 \mod nが成り立つ。
ここで\phi (n)オイラーのファイ関数と呼び、1以上n未満の整数に対し、nと違いに素な数字の個数です。

a,bが違いに素な整数というのはa,bが2以上の同じ素因数を持たないということです。
言い換えるとa,bの最大公約数が1とも言えます。
整数a,bに対してa,bの最大公約数(greatest common divisor)をgcd(a,b)と表現します。
つまりgcd(alb) = 1とも書けます。

唐突ですが、オイラーの定理でnを二つの素数p,qを掛けた値としておきましょう。
つまり、n=pqです。 このときのオイラーのファイ関数の値を算出してみます。
nが一般の整数の場合、ファイ関数の値を求めるのは大変ですが、条件がついた値なら値を求めるのは簡単です。
cが素数のとき、  {\phi ( c )} の値はc-1です。
なぜなら、cは素数なのでそれ未満の整数{1, 2, 3, …, c-1}はcを割り切れないからです。
nが2つの素数p, qの積(n=pq)の場合の \phi(n)はどうなるでしょうか。
1以上でn=pq未満の整数は全部でpq-1個あります。
1以上でpの倍数である集合P{p, 2p, 3p, … , (q-1)p}はpqと互いに素ではありませんからq-1個は取り除く必要があります。
同様に1以上、qの倍数である集合Q{q, 2q, 3q, …, (p-1)q}はpqと互いに素ではありませんからp-1個は取り除く必要があります。
ここでp,qを違いに素とするとこの集合P,Qは重複しないことがわかるので、結局
ファイ関数の値は \phi(pq) = pq-1-(q-1)-(p-1)=pq-q-p+1=(p-1)(q-1)となります。

ここで一つの定理を証明しておきます。

aを整数、p,qを異なる素数のとき、
 a \mod p = 1
 a \mod q = 1
であるとき、
 a \mod pq = 1 である。

証明:
k,lを整数とし、
a = pk +1 式(A)
a = qk + 1
と書けます。
したがって、pk=qlが成り立つ。
p,qは異なる素数なので、kはqの素因数を持ちます。つまり、mを整数とし、
k=qmと書けます。
式(A)に入れると
a = pqm + 1
つまり
 a \mod pq = 1
証明終わり。

eを、2以上(p-1)(q-1)未満で(p-1)(q-1)と互いに素な整数として選びます。
通常はeとして素数ではない数 65576={2}^{16} + 1= 2 * 2 * 2 * 7 * 1171 が使われます。
なぜこの値を使うのかに関してはさらに説明が必要なのでここでは省略します。
実装するときは、(p-1)(q-1)が65576と互いに素となるように素数p,qを選びます。

次にdを、2以上(p-1)(q-1)未満で
ed=1 mod (p-1)(q-1)となるように選びます。
つまり、kを整数として、ed = (p-1)(q-1)k +1と書けるようにd,kを選びます。
これが可能なことは次の定理が示しています。

定理
a,bを整数とするとき、
ax+by = gcd(a,b)
を満たす整数x,yが存在する。

この定理で、a=e, b=-(p-1)(q-1)と置くと、gcd(a,b)=1であり、 ex-(p-1)(q-1)y = 1を満たすxが存在するということです。
xが負の値になってしまった場合は、fと整数として
e(x + (p-1)(q-1)f)-(p-1)(q-1)(y + ef)=1
のように変形できるので、x'=x + (p-1)(q-1)fを正の値にできます。
この求めたxをdとします。

({m} ^ {e}) ^ {d} \mod p = {m} ^ {ed} \mod p = {m} ^ {(p-1)(q-1)k + 1} \mod p = {({m} ^ {(q-1)k})} ^ {p-1} m \mod p
オイラーの定理{a} ^ {p-1} \mod p = 1を用いると最後の式は、
 = 1 m \mod p = m \mod p
となります。 同様に、
 ({m} ^ {e}) ^ {d} \mod q = m \mod q
が成り立ち、少し前で証明した定理を用いると、
 ({m} ^ {e}) ^ {d} \mod pq = m \mod pq
これは、c= {m} ^ {e} \mod pqとしたときに、
 {c} ^ {d} = m \mod pq
となることを示しています。ここでn=pqで最初の暗号化が正しいことが分かりました。

実装する際はnのビット数が2048になるようにするので、p,qそれぞれが1024ビットの素数擬似乱数とミラーラビン法で選び、 p-1,q-1 がe=65537と互いに素であるようにし、pとqの値が異なるように選びます。
dはただ一つに決まります。

RSA暗号化方式を紐解く その(1)

感覚をつかむため、まずは実際の数値での例を見てみましょう。

RSA秘密鍵、公開鍵のペアを16bitの長さで生成してみました。
16bitを指定するとmodulusの大きさが16bitになります。

modulus:29353 秘密鍵
exponentE:65537 秘密鍵(通常65537固定なのであまり秘密ではない)
exponentD:15825 公開鍵
primeP:197
primeQ:149

ここでprivateキーがmodulesとexponentEであり、publicキーがexponentDです。
primePとprimeQは暗号化、復号化の際には使わず必要ありませんので、当面気にしなくて良いです。

modulusをn、exponentEをe、exponentDをdで表すことにします。
任意の平文m ( 0 \leq m < nとなる整数)を暗号化して暗号文c(整数)を作成してみましょう。
c = {m} ^ {e} \mod n
計算はpythonで行います。m=1234とすると、

>>> (1234 ** 65537) % 29353
13474L

暗号文c = 13474を復号化してみましょう。
m = {c} ^ {d} \mod n

>>> (13474 ** 15825) % 29353
1234L

元に戻りましたね。
なぜベキ乗とモジュロ演算を使うとうまく動作し安全な暗号が作れるのでしょうか。
徐々に見ていこうと思います。

次回に続く。

ビットコイン購入までの道のり その(1)

私がビットコインを入手した経緯は2015年に Bountysource というソフトウェアを作成したり、バグを直したりして報酬を得るサイトでバグを直したことによる報酬をビットコインで受け取ったことでした。2015年当時はUS DollorとBitCoinのどちらかが選べましたが、ビットコインに興味があったので、そちらを選び 0.7BTC(2015年時点で$200ほど)を入手しました。

ビットコインのドル為替チャートを見ると2016年後半から急激に値が上がり始めています。 2016年1月には1BTC=$430でしたが、2017年8月には1BTC=$4,300となり、10倍の価値となっています。もっとBTCを持っておけばよかったと思っても後の祭りです。

f:id:pebble8888:20170818172347p:plain

今後も下がることはなさそうなので、もう少し持っておこうと思い、追加購入するまでの道のりを記しておこうと思います。

日本円でBitcoinを買うにはどうすればいいのか?

ビットコインを報酬として受け取るだけなら、bitcoinのアドレスを管理してくれるサービスに登録するだけで良いです。ログインIDとパスワードを決めるだけです。ビットコインのアドレスはそのサービスが用意してくれます。このサービスへのログインは二段階認証を設定しておくのが普通です。私の場合、Blockchain というルクセンブルクにある会社が提供するサービスを使っています。 二段階認証はメールで行なっています。画面デザインはシンプルで使いやすいと思います。

日本円でビットコインを購入するにはいくつか方法があると思いますが、日本の普通銀行口座からの振込を使う場合、日本の取引会社を使うのが何かと安心なので仮想通貨ビットコイン(Bitcoin)の購入/販売所/取引所【bitFlyer】を使うことにします。

bitFlyerは振込について、日本のほとんどの銀行に対応しているようです。残念ながら信用金庫などには対応していないようです。私の場合三井住友銀行の普通口座を持っていたのでそれを使うことにしました。

bitFlyerではログイン時に二段階認証を設定していると確認コードを携帯電話(私の場合iPhone softbank)に送信してくれるのですが、私の携帯電話番号にはなぜか通知が来ません。仕方ないので音声による確認コード送信を選ぶと、自動音声による電話がかかって来て6桁のコードを喋ってくれます。ログインするたびにこの手順が必要で面倒なのですが、セキュリティレベルを下げたくないので仕方がありません。どうでもいいですが、この自動音声の"レー"(0) はどうやっても"レ"にしか聞こえませんので注意が必要です。
本人確認のため、免許証の裏と表をiPhoneで撮影した画像ファイルをuploadしたら数時間で認証OKとなりました。
銀行口座登録は銀行、支店名を選択し、口座情報を入れます。自宅電話番号と携帯電話番号は両方入れておく方が良いです。というのは振込の時に銀行口座には電話番号が登録されているので、その情報もある方が確定度が上がるためです。銀行口座の確認も数時間で認証OKとなりました。

三井住友銀行の場合は、自分の口座からbitFlyerの三井住友銀行の口座へ振り込みを行えば、bitFlyerの自分のアカウントにその金額があるとみなされます。 私の家には近くに三井住友銀行のATMも支店もないので、振込ができるローソンのATMを使いました。 一番近かったのはセブンイレブンだったのですが、セブン銀行のATMは振込サービスはやっておらず、預入、引出しかやっていないようでした。

次回に続く。

素数を高い確率で高速に判定するミラーラビン判定法

与えられた数が素数かどうかを高い確率で高速に判定するアルゴリズムとしてミラーラビン(Miller-Rabin)判定法があります。
暗号の実装で素数が必要な時にこの判定法が使われることが多いようです。 厳密に素数かどうかを判定する方法として、試行割算法(Trial Division)というものもありますが、 {10}^{6}を超える値に対しては、時間がかかりすぎてしまいます。 ミラーラビン判定法の数学上の根拠となる定理を見ていきます。

<定理1>
nは奇素数であり a は n と互いに素な整数であるとする。
n-1の素因数2を全てべきに抜き出し、
n-1 = {2} ^ {s} d
の形とする。この時、以下のi),ii)のどちらかが成り立つ。
i)  {a} ^ {d} = 1 \mod n
ii)  {a} ^ { {2} ^ {r} d } = -1 \mod n となるrが集合{0, 1, …, s-1}に存在する。

参考:
ミラー–ラビン素数判定法 - Wikipedia

この定理を使って、ミラーラビン判定法を定義します。
<ミラーラビン判定法>
判定したい奇数をnとする。
aを{1, 2, 3, …, n-1}からランダムに選び出す。
n-1の素因数2を全て抜き出し(奇数になるまで2で割り算する)、sとdを決定する。
 {a} ^ {d} \mod nを計算し、1であれば、[おそらく素数]とする。
全てのr:{0, 1, 2, …, s-1}に対して、
 {a} ^ { {2} ^ {r} d }  \mod nを計算し、-1であれば、[おそらく素数]とする。 上記以外の場合[おそらく合成数]とする。

このロジックに厳密性はなく、あくまでも素数である確率の判定法であることに注意する。
この判定法の確度はどのくらいなのかを示したが次の定理である。

<定理2>
nが奇数の合成数であるにも関わらず、
ミラーラビン判定法が[おそらく素数]を返すaの個数は{1, 2, 3, …, n-1}のうち、
約1/4である。

参考:
http://www.a-phys.eng.osaka-cu.ac.jp/suri-g/miller-rabin.pdf

定理2により、1回のミラーラビン判定の結果が、実際は合成数であるのに[おそらく素数]と判定 される確率は約1/4です。 この定理を使うと、合成数nに対して異なる整数a0, a1がともに[おそらく素数]の判定を下す 確率は約1/16となります。
つまり、異なるaに対してたくさん繰り返せば、誤判定をする確率を減らすことができるということです。

以下の論文によると、 kビットの数に対して、1回のミラーラビン判定が誤判定される確率は、
p_k \leq {k} ^ {2} {4} ^ { 2 - \sqrt {k} }
(k \geq 2) なので、
k=2048ビットに対しては {2} ^ { -63 }
k=4096ビットに対しては {2} ^ { -100 } となります。

https://math.dartmouth.edu/~carlp/PDF/paper88.pdf

ちなみに、opensslでは精度としては{2} ^ { -80}を想定してミラーラビン判定を行う回数を決定しているようで、 2048ビットや4096ビットなら2回となっています。

http://d.hatena.ne.jp/hnw/20140610

RSA with probable primes - Cryptography Stack Exchange

mod pでの平方剰余を計算する(p mod 8 = 5の場合)を実装する

少し前でp mod8 = 5の場合のmod p での平方剰余の計算方法を示しましたが、swiftで実装しておきます。
 {x} ^ {2} = a \mod p の解は存在すると仮定しておきます。

func quadraticResidue(_ a:Int, _ p:Int) -> Int {
    assert(p % 8 == 5)
    let x = expmod(a, (p+3)/8, p)
    if (x * x - a) % p == 0 {
        return x
    }
    let t = expmod(2, (p-1)/4, p)
    return t * x
}

mod p での平方剰余を計算する(p mod 4 = 3の場合)

前回、p mod 8 = 5の時の平方剰余を計算しましたが、今回は、
p mod 4 = 3の時の平方剰余を計算してみましょう。
この場合も簡単に計算が可能です。 前回と同じように
 {x} ^ {2} = a
の解は存在することを仮定します。つまり、
 ( \frac {a} {p}) = 1
です。
 p = 4k + 3と書けます。
解は、
 x = {a} ^ {k + 1}
となります。なぜなら、
 {x} ^ {2} = {a} ^ {2k +2} = {a} ^ {2k+1} a = {a} ^ { \frac {p-1} {2} } a
オイラーの基準を使い、右辺は、
 = ( \frac {a} {p} ) a = a
となり、式を満たします。 解をpで書くと
 x = {a} ^ { \frac {p+1} {4} }
となります。

mod pでの平方剰余を計算する(p mod 8 = 5の場合)

pをある程度限定した素数とした時の平方剰余を計算してみます。
整数論の世界では実数の世界でのルートという言葉は使わないようです。

いくつかの整数論の定理を利用しますので、事前に明示しておきます。
これらの定理は超有名なので、整数論の本に必ず載っています。

オイラーの基準(Euler’s Criterion)
pを奇素数, aを整数とする.この時,
 ( \frac {a} {p} ) = {a}^{ \frac {p-1} {2} } \begin{eqnarray} \bmod p \end{eqnarray}

平方剰余の第2補充法則
pを奇素数とすると,
 p = 1,7 \begin{eqnarray} \bmod 8 \end{eqnarray}の場合
 ( \frac {2} {p} ) = 1
 p = 3,5 \begin{eqnarray} \bmod 8 \end{eqnarray}の場合
 ( \frac {2} {p} ) = -1
ここでカッコはルジャンドル記号と言います.

本題
素数pとしてp mod 8 = 5の場合だけを考えます。
この時, p mod 4 = 1でもあります。
この素数の例としては {2} ^ {255} - 19があります。

p = 8k + 5と書けます。また \frac {p-1} {4}は整数です。

 {x} ^ {2} = a\mod p の解は存在すると仮定して、解xを求めたいです。
解が存在するということは、
 ( \frac {a} {p} ) = 1です。 オイラーの基準を使うと、
 {a} ^ { \frac {p-1} {2} } = ( \frac {a} {p} ) = 1\mod p

 \frac {p-1} {4}は整数なので、左辺は  {a} ^ { \frac {p-1} {4} 2}となり、
ケースa)  {a} ^ { \frac {p-1} {4} } = 1 \mod p
ケースb)  {a} ^ { \frac {p-1} {4} } = -1 \mod p
のどちらと言えます。

a)の場合は、  x = {a} ^ {k+1}が解となります。
なぜなら、
 {x} ^ {2} = {a} ^ {2k+2} = {a} ^ { \frac {p-5} {4} + 2} = {a} ^ { \frac {p-1} {4}} a = a\mod p
となるからです。
b)の場合は、
 x = {2} ^ {2k+1} {a} ^ {k+1}が解となります。
なぜなら、
 {x} ^ {2} = {2} ^ {4k+2} {a} ^ {2k+2} = {2} ^ { \frac {p-1} {2} } {a} ^{ \frac {p-1} {4}} a = {2} ^ { \frac {p-1} {2} } (-1) a\mod p
ここでオイラーの基準でa=2と置いた式を使うと
  ( \frac {2} {p} ) = {2}^{ \frac {p-1} {2} } \begin{eqnarray} \bmod p \end{eqnarray}
平方剰余の第2補充法則を使うと、
この左辺は-1なので結局、最後の式は (-1) (-1) a = a\mod pとなり、解となっていることが分かりました。
まとめると、解は、
a)の場合
 x1= {2} ^ { \frac {p-1} {4}} {a} ^ {\frac {p+3} {8} }
であり、
b)の場合
 x2= {a} ^ { \frac {p+3} {8} }
となることが分かりました。
どちらも同じ因子が現れていますね。
コンピュータで計算する場合は、場合分けの計算を省くために、この因子を先に計算し、その二乗を計算して、aに一致するか確かめます。
一致すればb)の場合なので、そこで終了です。一致しない場合はa)の場合なので、さらに2のベキ乗因子を計算して掛ければ解が得られます。

参考: http://course1.winona.edu/eerrthum/13Spring/SquareRoots.pdf