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

2017-05-17

swift3 IntegerArithmaticプロトコル

swift

IntegerArithmeticプロトコルを実装するには、以下8つの関数を定義する必要がある。最初の２つはComparableである。

static func ==(lhs: M, rhs: M) -> Bool
static func <(lhs: M, rhs: M) -> Bool
static func addWithOverflow(_ lhs: M, _ rhs: M) -> (M, overflow: Bool) 
static func subtractWithOverflow(_ lhs: M, _ rhs: M) -> (M, overflow: Bool) 
static func multiplyWithOverflow(_ lhs: M, _ rhs: M) -> (M, overflow: Bool) 
static func divideWithOverflow(_ lhs: M, _ rhs: M) -> (M, overflow: Bool) 
static func remainderWithOverflow(_ lhs: M, _ rhs: M) -> (M, overflow: Bool) 
func toIntMax() -> IntMax

最後の一つはswiftの最大Int(=UInt64)へ変換するものである。このプロトコルを実装すると以下の５つの演算や関連する演算ができるようになる。

public static func +(lhs: Self, rhs: Self) -> Self
public static func -(lhs: Self, rhs: Self) -> Self
public static func *(lhs: Self, rhs: Self) -> Self
public static func /(lhs: Self, rhs: Self) -> Self
public static func %(lhs: Self, rhs: Self) -> Self

このプロトコルを用いると、通常とは異なる演算規則を持つ整数を作ることができる。複素整数や桁数が無制限の整数などを自作することができる。

2017-05-17

swift3 Comparableプロトロル

swift

Comparableプロトコルを作るには、
static func <(lhs: Even, rhs: Even) -> Bool
static func ==(lhs: Even, rhs: Even) -> Bool
の２つを実装すればよい。

struct M : Comparable 
{
    var val:Int
    
    static func <(lhs: M, rhs: M) -> Bool 
    {
        return lhs.val < rhs.val
    }
    
    static func ==(lhs: M, rhs: M) -> Bool
    {
        return lhs.val == rhs.val
    }
}

let r1 = M(val:1)
let p1 = M(val:2)
assert(r1 < p1)

let r2 = M(val:1)
assert(r1 == r2)