2017-06-18

楕円曲線の形

暗号

楕円曲線の一般的な形は以下のように表せます。

$y^{2} = x^{3} + ax^{2} + bx + c$

暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。
特異でない形のものは２つのパターンに分けられます。
1) yが0の時のxの値が３つある場合
2) yが0の時のxの値が１つだけしかない場合
それぞれの例を挙げます。

1) $y^{2} = x^{3} + x^{2} - x$

これは、左の曲線が閉じているパターンです。

2) $y^{2} = x^{3} + x^{2} + 1$

これは開いているパターン。

このグラフのイメージを掴んでおくと、楕円曲線の理論がとても理解しやすくなります。

a) この曲線上の２つの点を結ぶ直線を引くと、曲線と交わる３番目の点は必ず存在します。
b) xをプラスの無限大に持っていくと、yがプラスの無限大とマイナスの無限大に近づきます。

楕円曲線論入門

作者: J. H.シルヴァーマン,J.テイト,Joseph H. Silverman,John Tate,足立恒雄,木田雅成,小松啓一,田谷久雄
出版社/メーカー: 丸善出版
発売日: 2012/08/25
メディア: 単行本
この商品を含むブログを見る

2017-06-17

群、体、有限体の定義

群環体

群(group)の定義

ある要素の集まりに対して、一つの演算規則 f を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, c を要素とします。

1) 全ての要素に対して、結合法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
2) 全ての要素に対して、単位元が存在する
3) 全ての要素に対して、逆元が存在する

体(field)の定義

ある要素の集まりに対して、加算 f と乗算 g を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, cを要素とします。
1) 加算について可換群(単位元と逆元が存在する)
2) 乗算について可換群(単位元と逆元が存在する)
3) 加算、乗算について分配法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
g(f(a, b), c) = g(a, g(b, c))

体の元の数を位数と呼びます。

例1:

整数の集合は体ではありません。
なぜなら 3 を乗算する演算の逆元は 1/3 だが、これは整数ではなく有理数になってしまうから。

例2:

有理数の集合は体です。

有限体

整数の集合に対して、
加算を「整数の加算後に素数pで割った余り」
乗算を「整数の乗算後に素数pで割った余り」と定義した場合、体となります。
つまり、全ての要素に対して逆元が存在します。
元の数は p となります。
この体を $F_{p}$ と書きます。

2017-06-10

離散対数問題(Discrete Logarithm Problem)とは

暗号

RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、
楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。

離散対数問題(DLP)をここで解説してみます。

p : 素数

これは説明不要ですね。 2,3,5,7,11,...のように自分自身の値未満の数で割り切れる値が1だけな正の整数値です。

mod : モジュラ演算

a mod b = c

整数aを整数bで割った余りがcであることを表します。例えば、

7を3で割った余りは1
7 mod 3 = 1

8を3で割った余りは2
8 mod 3 = 2

9を3で割った余りは0
9 mod 3 = 0

余りは必ず、0からb-1の値のどれかになる性質があります。

原始根

3以上の素数 p と 1 以上 p-1 以下の整数 r が以下の性質を満たすとき r を mod p の原始根と呼びます。
「 $r, r^{2}, ⋯, r^{p−2}$ のいずれもが p で割って余り 1 でない。」

p=13の場合、原始根は2,6,7,11であることが知られていますが、原始根2の場合で計算してみます。

$2 \bmod 13 = 2$

$2^{2} \bmod 13 = 4$

$2^{3} \bmod 13 = 8$

$2^{4} \bmod 13 = 16 \bmod 13 = 3$

$2^{5} \bmod 13 = 32 \bmod 13 = 6$

$2^{6} \bmod 13 = 64 \bmod 13 = 12$

$2^{7} \bmod 13 = 128 \bmod 13 = 11$

$2^{8} \bmod 13 = 256 \bmod 13 = 9$

$2^{9} \bmod 13 = 512 \bmod 13 = 5$

$2^{10} \bmod 13 = 1024 \bmod 13 =10$

$2^{11} \bmod 13 = 2048 \bmod 13 = 7$

余りがいずれも1ではないことは確認できましたが、それ以外に何か気がついたでしょうか？
右辺の計算結果が2から12までの数字になっていて重複がないですね。
さらに、対応に規則性はないように見えますね。

同様に、原始根6の場合でも試してみましょう。

$6 \bmod 13 = 6$

$6^{2} \bmod 13 = 36 \bmod 13 = 10$

$6^{3} \bmod 13 = 216 \bmod 13 = 8$

$6^{4} \bmod 13 = 1296 \bmod 13 = 9$

$6^{5} \bmod 13 = 7776 \bmod 13 = 2$

$6^{6} \bmod 13 = 46656 \bmod 13 = 12$

$6^{7} \bmod 13 = 279936 \bmod 13 = 7$

$6^{8} \bmod 13 = 1679616 \bmod 13 = 3$

$6^{9} \bmod 13 = 10077696 \bmod 13 = 5$

$6^{10} \bmod 13 = 60466176 \bmod 13 = 4$

$6^{11} \bmod 13 = 362797056 \bmod 13 = 11$

原始根6の場合もやはり重複していませんし、対応に規則性も見えません。

原始根を使うと、この数式の右辺の値(=2からp-1までの値)と、左辺のべき乗の値が一対一対応させられるという性質があります。つまり、

p:素数、g:原始根、A: { 2, 3, 4, ..., p-1 }(右辺値)、r: { 1, 2, 3, ..., p-2 } (べき乗値)
$g^{r} \bmod p = A$

と書いた時に、rとAが一対一対応するということになります。

ここで計算したように、Aの値を与えた時に、対応するrの値を求めるには、べき乗計算とモジュラ計算を、
(計算量が少なくなるように)次数の少ない方から順番に計算し、余りがAになるまで繰り返す必要があります。
これを簡単に計算する一般的な方法は見つかっていないそうです。
これが、離散対数問題と呼ばれるものです。

Aの値を与えた時に、べき乗の値を返す関数を一般に対数関数と呼びますが、
ここで、rのことを底gについてのAの離散対数と呼びます。

一対一対応する値のペアがあり、計算が難しいということは、暗号に使えそうな気がしてきますね。

ここでやった単純なモジュラ演算の部分を楕円曲線上の演算に置き換えたものが、楕円曲線上のDLPというものです。

楕円曲線における離散対数問題(ECDLP)についてはこちら

楕円曲線における離散対数問題 - Pebble Coding

参考:
原始根の定義と具体例（高校生向け） | 高校数学の美しい物語

暗号技術入門第3版

作者:結城浩
SBクリエイティブ

Amazon

2017-06-08

安全素数

整数論

pが素数であり、2p+1=qも素数である場合、qを安全素数(safe prime)と呼ぶ。
安全という名前は暗号理論に由来する。

https://en.wikipedia.org/wiki/Safe_prime

https://ja.wikipedia.org/wiki/安全素数

2017-05-27

iOSでRSAを使いメッセージを暗号化してみる(SwiftyRSA)

暗号

iOSでRSAを使ってメッセージを暗号化してみます。
SwiftRSA
https://github.com/TakeScoop/SwiftyRSA
というライブラリを利用します。
RSAの実装は、AppleのSecurity.Frameworkが利用されています。
macOS版はサポートされていないようです。

サンプルiOSアプリを作り、CocoaPodを使ってフレームワークをリンクします。

pod 'SwiftyRSA'

opensslコマンドを使って、RSAの鍵ペアを作ります。

$ openssl genrsa 2048 > private-key.pem
...+++
......+++
e is 65537 (0x10001)
$ openssl rsa -in private-key.pem -pubout -out public-key.pem
writing RSA key

できた２つのファイルはこのようになっています。

$ cat private-key.pem 
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAvwLN8/7d+VIDVqZ3T1PFf3fohfhzJkN9ZhGdk+lii4YQ/ywG
Wwf2pp5786+ZIxCseUUcWRn0flk44rCRwdxbkPlb+s8dWnLcyggMz71DbcdGxGhA
mCMP8XlD/m2Oa7UMyHGnL/JXf3gCSrAmeP7qMWviSw2MElmkbQxWJ86kY8Lq7Pua
LJJ83RdNHiAN5+gRQPAWZxVQAXggae7XUFAwYfmtic09JLu5oHmW/1ha82kXReK7
tczDCl6B++3I2GsIV3zHo6STENvggTXQtsyej7Lo+oQekTXpXfalRql5L5WTRYU1
I8H/zNy/GFQXQSdzvwQ2k1E5kbol+nUMjrrzaQIDAQABAoIBAQCjVxedvmY9rXdz
YtkGOiHatkReRC7cGryiSxAQi3Sc0aG5RAGPWMkAhOiEY7Y1uS10argqLbrZTR0L
JWkPeYvH9qVEXlbAoRbToXyrLTL7Ln0Cug/6yYj5uvR9H1y6GFH9GsuYgcl3FL4I
9od/0qWca6BRBB2zF3s3UWRfmCMVtv3LnAarO1v5d8GKz4220/FHueEHoHaQCE9j
PRWEbiTlzrO+jTY7hr2xpC2sUz2TiOeQijD4eVOZsrup0r4Wxn4+hS02yvD5/Zqu
6KP5xW8eCvQu0DRHw0E/7pv89d17LX1l4lXvb3cqDuX4rvM4kwx+HjFodKeelMm0
8xfiU1FtAoGBAPa9Yqmdt2599XhOXY7croXW4Eq4StHkO0x2GNejQzp62vwgH8Lf
8uxad4ZFTQiMtiu0ar/0awIxd6A8Ov8SivB5pdGkCOiovl2xn8SdxEsMQon4ydZD
BbKdnDdMmXpdZhU9mOnftg5iDKVv3r+JvuX/mzBalUN/J3NsJ0E7AonzAoGBAMYt
/YYm1bl0alL77THd+NI7d9qfRFYkg8+/W4Uqo1XD8t//9457oawKQ8quEB5fonv+
pvnR8/HY5VKQlmrO3e/kgvHCc7hhWiNOmH8GWQ0QlTOEQkFcwe9gc0w3ntY69JrH
nMtzrK5NjhkjoyVHlaAExDTs90CjYicijoI9BqgzAoGBAJlC4foBoWLckpD7/Fk0
8qLn6cH/31morry7zoqDOsskbMmXGqNtf/MX7o5UlZjt7moPUw+QvrdKCshZITw3
RF5C8aDahz4dMsH4BwmWBcun/dy90IFqeCuOgu5Ggj7jrPkcndMHxooAlWJdrrrC
0PUEZF0Qpw6Z+ONVFr0J7nXJAoGAFu41WnNd4WJ99vIdZNq5MqIc4RfykUESW1RZ
45OmaIMOtCpq23qkn0Jky6vOQ6VvKIezjE5luoMNLbt7HAqplVtMZ2rHdvsUsecj
L/dtEFzt1pMkE2oHKopvbM82urUBnnMgSk4tGdHxcik0dFjPED/c7/7HMRx2e+68
rIchIQ8CgYA+0wBpkDIpkK2EEw6GVRHAtJ8amMEpsG2sCE8TkHdhL5Oi0jcLpcoN
R4JPWLDrGEwHXe38b8jfgdl2oe0eQS3mnDFSj82hIjJEgkZDpjVq9M2m8hBLgbV7
eBsJr5dJq6OvULI7clWaRBpFaekUtoxzeozCwK4xEcYKfDdce4aOdA==
-----END RSA PRIVATE KEY-----
$ cat public-key.pem 
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAvwLN8/7d+VIDVqZ3T1PF
f3fohfhzJkN9ZhGdk+lii4YQ/ywGWwf2pp5786+ZIxCseUUcWRn0flk44rCRwdxb
kPlb+s8dWnLcyggMz71DbcdGxGhAmCMP8XlD/m2Oa7UMyHGnL/JXf3gCSrAmeP7q
MWviSw2MElmkbQxWJ86kY8Lq7PuaLJJ83RdNHiAN5+gRQPAWZxVQAXggae7XUFAw
Yfmtic09JLu5oHmW/1ha82kXReK7tczDCl6B++3I2GsIV3zHo6STENvggTXQtsye
j7Lo+oQekTXpXfalRql5L5WTRYU1I8H/zNy/GFQXQSdzvwQ2k1E5kbol+nUMjrrz
aQIDAQAB
-----END PUBLIC KEY-----

opensslコマンドで暗号化を行ったメッセージをiOSアプリで復号できるかやってみます。

$ echo -n "hogefuga" > msg.bin
$ openssl rsautl -encrypt -pubin -inkey public-key.pem -in msg.bin -out encrypted_msg.bin

作成されたencrypted_msg.binファイルとprivate-key.pemファイルをiOSプロジェクトに追加します。

import SwiftyRSA
do {
    let privatekey:PrivateKey = try PrivateKey(pemNamed: "private-key")
    let url:URL = Bundle.main.url(forResource: "encrypted_msg", withExtension: "bin")!
    let data:Data = try Data(contentsOf: url)
    let encrypted:EncryptedMessage = EncryptedMessage(data: data)
    let decrypted:ClearMessage = try encrypted.decrypted(with: privatekey, padding: .PKCS1)
    print("\(try decrypted.string(encoding: .utf8))")
} catch {
    fatalError()
}

実行結果

hogefuga

参考
公開鍵暗号をプログラムで扱う方法のまとめ - Qiita