Pebble's Diary

プログラマーの作業メモ

エドワード曲線における加法

エドワード曲線 
x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}

において、曲線上の2つの点  (x_{1}, y_{1}), (x_{2}, y_{2}) の加算後の点を次のように定義する。

 \displaystyle X = \frac {1} {a} \cdot \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + x_{1} x_{2} y_{1} y_{2}}

 \displaystyle Y = \frac {1} {a} \cdot \frac {y_{1} y_{2} - x_{1} x_{2}} {1 - x_{1} x_{2} y_{1} y_{2}}

この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。  

 A = X^{2} + Y^{2} - a^{2}X^{2}Y^{2}を計算し、 a^{2}に等しくなることを示す方針で行く。

代入すると  \displaystyle a^{2} A = \frac {1} {(1 + x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ (x_{1}y_{2} + x_{2}y_{1})^{2}(1- x_{1}x_{2}y_{1}y_{2})^{2} \\ + (y_{1}y_{2} - x_{1}x_{2})^{2} (1 + x_{1} x_{2} y_{1} y_{2})^{2} \\ - (x_{1}y_{2} + x_{2}y_{1})^{2} (y_{1}y_{2} - x_{1}x_{2})^{2})

ここで、

 \displaystyle a^{2}A(1 - x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2}) = B + C + Dと置く。

B + C + Dを全て展開し、 x_{1}, x_{2}, y_{1}, y_{2}の順番で並べると、7つほどペアが消える。

 B + C + D = x_{1}^{2}y_{2}^{2} + x_{2}^{2}y_{1}^{2} + x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} + x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} \\
+ y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2} - 4 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} + x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} \\
- x_{1}^{2}y_{1}^{2}y_{2}^{4} - x_{2}^{2}y_{1}^{4}y_{2}^{2} - x_{1}^{4}x_{2}^{2}y_{2}^{2} - x_{1}^{2}x_{2}^{4}y_{1}^{2}  \\
= E_{4} + E_{8} + E_{12}

ここでE_{i}はx,yの個数を表すが、それぞれ別々に計算してゆくと、 E_{4}, E_{8}, E_{12}には、  x_{1}^{2} + y_{1}^{2},  x_{2}^{2} + y_{2}^{2}が2つ以上出てくるので、  x_{1}^{2} + y_{1}^{2} = a^{2} ( 1 + x_{1}^2 y_{1}^2)
 x_{2}^{2} + y_{2}^{2} = a^{2} ( 1 + x_{2}^2 y_{2}^2) に置き換える。

ここで、  \frac {1} {a^{4}} (E_{4} + E_{8} + E_{12})を計算すると、5つほどペアが消え、  1 - 2 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} +  x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}が残る。 あとは簡単である。

エドワード曲線とツイストエドワード曲線

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf)

から、エドワード曲線と名付けられた


x^{2} + y^{2} = a^{2}(1 + x^{2} y^{2})

がどのような形をしているのか見てみましょう。

まずはa=1.0

2本の直線になってしまいました。。

次にa=1.1

次にa=0.9

おっと丸くなりました。

次に、ツイストエドワード曲線(http://eprint.iacr.org/2008/013.pdf)


a x^{2} + y^{2} = 1 + d x^{2} y^{2}

をみてみましょう。

a=1, d= -50

a=-1, d=-50

a=-1, d=5

楕円曲線の形

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


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

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

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

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

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

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

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

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

楕円曲線論入門

楕円曲線論入門

群、体の定義

群(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))

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

ガロア体(galois field)

整数の集合に対して、
加算を「整数の加算後に素数pで割った余り」、乗算を「整数の乗算後に素数pで割った余り」とした場合、
これは位数 p の体となることが知られています。
つまり、全ての要素に対して逆元が存在します。 この体をGF(p)と書きます。

離散対数問題とは

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

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

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 = 1,296 \bmod 13 = 9

 6^{5} \bmod 13 = 7,776 \bmod 13 = 2

 6^{6} \bmod 13 = 46,656 \bmod 13 = 12

 6^{7} \bmod 13 = 279,936 \bmod 13 = 7

 6^{8} \bmod 13 = 1,679,616 \bmod 13 = 3

 6^{9} \bmod 13 =  10,077,696 \bmod 13 = 5

 6^{10} \bmod 13 = 60,466,176 \bmod 13 = 4

 6^{11} \bmod 13 = 362,797,056 \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の離散対数と呼びます。

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

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

暗号理論入門 原書第3版

暗号理論入門 原書第3版

安全素数

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

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

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

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

iOSRSAを使ってメッセージを暗号化してみます。
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

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

$ 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