2017-08-27

楕円曲線暗号情報リンクまとめ

暗号

ECDSA ( Elliptic Curve Digital Signature Algorithm )のWiki(日本語)
楕円曲線DSA - Wikipedia
ECDSA のWiki(英語)
Elliptic Curve Digital Signature Algorithm - Wikipedia
EdDSA ( Edwards-Curve Digital Signature Algorithm ) のWiki
EdDSA - Wikipedia
EdDSAのRFC 8032
RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
Ed25519のpythonによるサンプル実装、主要論文のリンク
https://ed25519.cr.yp.to/software.html
SUPERCOPによる様々な暗号のC言語実装
https://bench.cr.yp.to/supercop.html
wgetでソースを取得できる。
ed25519の実装は、解凍後のcrypto_sign/ed25519にある。
鍵ファイル仕様
EdDSA, Ed25519, Ed448, Curve25519 and Curve448 for X.509 (鍵ファイルフォーマット)(仕様策定中)
https://tools.ietf.org/html/draft-ietf-curdle-pkix-00
RSA暗号 RFCリンク
RSA暗号の全体像 - Qiita
NaClによるC言語実装
GitHub - jedisct1/libsodium: A modern, portable, easy to use crypto library
RFC7748 Elliptic Curves for Security
RFC 7748 - Elliptic Curves for Security

2017-08-19

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(a,b) = 1とも書けます。

唐突ですが、オイラーの定理でnを二つの素数p,qを掛けた値としておきましょう。
つまり、n=pqです。このときのオイラーのファイ関数の値を算出してみます。
nが一般の整数の場合、ファイ関数の値を求めるのは大変ですが、条件がついた値なら値を求めるのは簡単です。
cが素数のとき、 ${\phi ( c )}$ の値はc-1です。
なぜなら、cは素数なのでそれ未満の整数{1, 2, 3, ..., c-1}はcを割り切れないからです。
nが２つの素数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 = ql + 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はただ一つに決まります。

2017-08-19

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

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

次回に続く。

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

2017-08-18

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

仮想通貨

私がビットコインを入手した経緯は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 - Most Trusted Crypto Company というルクセンブルクにある会社が提供するサービスを使っています。二段階認証はメールで行なっています。画面デザインはシンプルで使いやすいと思います。

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

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

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

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

次回に続く。

2017-08-14

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

整数論

与えられた数が素数かどうかを高い確率で高速に判定するアルゴリズムとしてミラーラビン(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=256ビットに対しては ${2}^{-12}$
k=2048ビットに対しては ${2} ^ { -63 }$
k=4096ビットに対しては ${2} ^ { -100 }$ となります。