Pebble's Diary

プログラマーの作業メモ

lets encryptでエラーが出ていたので修正

lets encrypt で https 化していたサイトがあと1ヶ月で切れますよメールがきて、どうやら自動更新に失敗していると気がつく。

/root/letsencrypt/letsencrypt-auto certonly --webroot --webroot-path /home/onsenlife/public -d onsenlife.info --renew-by-default
Saving debug log to /var/log/letsencrypt/letsencrypt.log
Renewing an existing certificate
Performing the following challenges:
http-01 challenge for onsenlife.info
Using the webroot path /home/onsenlife/public for all unmatched domains.
Waiting for verification...
Cleaning up challenges
Failed authorization procedure. onsenlife.info (http-01): urn:acme:error:unauthorized :: The client lacks sufficient authorization :: Invalid response from http://onsenlife.info/.well-known/acme-challenge/5nYAmxnZX5Vzx9mzgQG6qmKaZmnTi7YHnTRmDHfwH3c: "<html>
<head><title>404 Not Found</title></head>
<body bgcolor="white">
<center><h1>404 Not Found</h1></center>
<hr><center>"

IMPORTANT NOTES:
 - The following errors were reported by the server:

   Domain: onsenlife.info
   Type:   unauthorized
   Detail: Invalid response from
   http://onsenlife.info/.well-known/acme-challenge/5nYAmxnZX5Vzx9mzgQG6qmKaZmnTi7YHnTRmDHfwH3c:
   "<html>
   <head><title>404 Not Found</title></head>
   <body bgcolor="white">
   <center><h1>404 Not Found</h1></center>
   <hr><center>"

   To fix these errors, please make sure that your domain name was
   entered correctly and the DNS A/AAAA record(s) for that domain
   contain(s) the right IP address.

どうやら、今はcertbotをインストールしてやるのがいいらしい。

certbot.eff.org

このサイトの指示に従えばオッケーだ。 nginxとcentos7を選択して出てきたコマンドを打ってみる。

# yum -y install yum-utils
# yum -y install epel-release
# sudo certbot --nginx

Saving debug log to /var/log/letsencrypt/letsencrypt.log
Starting new HTTPS connection (1): acme-v01.api.letsencrypt.org

Which names would you like to activate HTTPS for?
-------------------------------------------------------------------------------
1: onsenlife.info
-------------------------------------------------------------------------------
Select the appropriate numbers separated by commas and/or spaces, or leave input
blank to select all options shown (Enter 'c' to cancel):1
Cert is due for renewal, auto-renewing...
Renewing an existing certificate
Performing the following challenges:
tls-sni-01 challenge for onsenlife.info
Waiting for verification...
Cleaning up challenges
Deployed Certificate to VirtualHost /etc/nginx/conf.d/onsenlife.conf for set(['onsenlife.info'])

Please choose whether HTTPS access is required or optional.
-------------------------------------------------------------------------------
1: Easy - Allow both HTTP and HTTPS access to these sites
2: Secure - Make all requests redirect to secure HTTPS access
-------------------------------------------------------------------------------
Select the appropriate number [1-2] then [enter] (press 'c' to cancel): 2
The appropriate server block is already redirecting traffic. To enable redirect anyway, uncomment the redirect lines in /etc/nginx/conf.d/onsenlife.conf.

-------------------------------------------------------------------------------
Your existing certificate has been successfully renewed, and the new certificate
has been installed.

The new certificate covers the following domains: https://onsenlife.info

You should test your configuration at:
https://www.ssllabs.com/ssltest/analyze.html?d=onsenlife.info
-------------------------------------------------------------------------------

IMPORTANT NOTES:
 - Congratulations! Your certificate and chain have been saved at
   /etc/letsencrypt/live/onsenlife.info/fullchain.pem. Your cert will
   expire on 2017-10-09. To obtain a new or tweaked version of this
   certificate in the future, simply run certbot again with the
   "certonly" option. To non-interactively renew *all* of your
   certificates, run "certbot renew"
 - If you like Certbot, please consider supporting our work by:

   Donating to ISRG / Let's Encrypt:   https://letsencrypt.org/donate
   Donating to EFF:                    https://eff.org/donate-le

cronには

certbot renew

を書けばよいとある。 1日に2回くらい実行するとよいと書いてあるので毎日5:00に実行するようにしてみた。

# crontab -l
00 05 * * * certbot renew 

mod p の世界では、割り算をべき乗計算に置き換えられる

フェルマーの小定理でpを素数とすると、mod pの世界では、割り算をべき乗に置き換えられます。
pを3以上の素数としておきます。
フェルマーの小定理
 b ^ { p -1 } = 1\mod p
で、pは3以上なので、
 b ^ { p - 2 } \times b = 1\mod p
と書けます。これは mod p においては、乗算に対して、bの逆元が  b ^ { p -2 }であることを示しています。
つまり、bで割り算をしたかったら、 b ^ { p - 2}で掛け算をすればよいわけです。
そういえば、少し前で  b ^ { e }\mod m を計算する関数を作りましたよね?
ここでズバリ割り算をする関数を作ります。関数名はinversemodとしておきます。

func inversemod(b:Int, p:Int) -> Int {
    return expmod(b, p - 2, p)
}

オイラーの φ 関数 とフェルマーの小定理

1以上の整数であるmで割った余りの値を同一とみなす演算の世界では元の数はm-1個である。
gcd(a, m) = 1である数aの総数をオイラー \phi関数と呼ぶ。
小さい方からどのような数なのかみておく。
1: {1} -> 1
2: {1} -> 1
3: {1, 2} -> 1
4: {1, 3} -> 2 (2は除外)
5: {1, 2, 3, 4} -> 4
6: {1, 5 } -> 2 (2, 3, 4は除外)
7: {1, 2, 3, 4, 5, 6} -> 6
8: {1, 3, 5, 7} -> 4 (2, 4, 6は 除外)
9: {1, 2, 4, 5, 7, 8} -> 6 (3, 6は除外)

よく知られたように素数pの場合は{1, 2, …, p-1}が全てgcd(a, p) = 1となるから、
 \phi(p) = p-1
である。

フェルマーの小定理

 gcd(a, m) = 1 であれば、a ^ { \phi(m)} = 1\mod m

高速指数計算法 mod m バージョン

前回書き下した再帰を用いた高速指数計算関数をmod mバージョンにして、7を一般化した数bにしてみよう。 するとこうなる。関数名はpowからexpmodに置き換えた。

func expmod(b:Int, e:Int, m:Int) -> Int {
    if e == 0 { return 1 }
    let s = expmod(e/2) % m
    // 2乗する
    let r = (s * s) % m
    if isOdd(e) {
        return (r * b) % m
    } else {
        return r
    }
}

 b ^ { e }\mod mを計算したい場合はこの関数を使えばよい。

高速指数計算法アルゴリズム

ある数の大きなべき数を計算を行う際にできるだけ少ない計算量で行うための方法として、高速指数計算法というものがある。

例えば、
 7 ^ {1281}
を計算したいとする。ここで
1281 = 1 + 256 + 1024 = 2 ^ {0} + 2 ^ {8} + 2 ^ {10} = 2 ^ {0} \times 1 + 2 ^ {1} \times 0 + 2 ^ {2} \times 0 + \ldots + 2 ^ {10} \times 1
のように2の累乗の足し算に分解する。
そして、  7 ^ {1281} = 7 ^ {1} \times 7 ^ {256} \times 7 ^ {1024} を計算する。
この分解をプログラムで行う場合には、順番に値を2で割り算し、その値が奇数であるかどうか判定し、値が0になるまで繰り返せばよい。 やってみよう。

0: 1281 -> odd  7 ^ {1}
1: 640 -> even  7 ^ {2}
2: 320 -> even  7 ^ {4}
3: 160 -> even  7 ^ {8}
4: 80 -> even  7 ^ {16}
5: 40 -> even  7 ^ {32}
6: 20 -> even  7 ^ {64}
7: 10 -> even  7 ^ {128}
8: 5 -> odd  7 ^ {256}
9: 2 -> even  7 ^ {512}
10: 1 -> odd  7 ^ {1024}
11: 0 -> 終わり

oddの部分の7の冪乗部分の3つを掛け算すれば答えが得られるが、この繰り返し処理の中で、
7の冪乗の値は一つ前で計算した値の2乗になっているので、計算量が最小限に抑えられるのである。

再帰を使わずにswiftで書くとこんな感じになる。

func pow(e:Int) -> Int {
    var b:Int = 7
    var r:Int = 1
    while e > 0 {
        if isOdd(e) { r *= b }
        // 2乗する
        b = b * b
        // 2で割る
        e /= 2
    }
    return r
}

再帰を使った場合はこんな感じになる。

func pow(e:Int) -> Int {
    if e == 0 { return 1 }
    let s = pow(e/2)
    // 2乗する
    let r = s * s
    if isOdd(e) {
        return r * 7
    } else {
        return r
    }
}

 pow(1281) = pow(640) ^ {2} \times 7
 pow(640) = pow(320) ^ {2}
 pow(320) = pow(160) ^ {2}
 pow(160) = pow(80) ^ {2}
 pow(80) = pow(40) ^ {2}
 pow(40) = pow(20) ^ {2}
 pow(20) = pow(10) ^ {2}
 pow(10) = pow(5) ^ {2}
 pow(5) = pow(2) ^ {2} \times 7
 pow(2) = pow(1) ^ {2}
 pow(1) = 7

再帰を使った場合は見ての通りvarの変数を一つも使っておらずとても綺麗なロジックになる。

curve25519とed25519の同等性

curve25519とは、
\nu^{2} = \mu^{3} + 486662\mu^{2} + \mu
のことであり、
ed25519とは、
x^{2} + y^{2} = 1 +\frac {121665}{121666} x^{2}y^{2}
のことである。 これは単純な変数の置き換えで同等性が示せる。
ただし、ed25519の方が加法定義で場合分けをする必要がなく、扱いやすい。

 d = 486662 とし、  \frac {d - 2}{d + 2} = \frac {121665} {121666} とする。

\nu = \sqrt{d} \frac {\mu} {x}
\mu = \frac {1+y} {1-y}
を代入して計算すると、
(2+d)x^{2} + dy^{2} = d + (d-2)x^{2}y^{2}
となる。
xをx \sqrt{ \frac {d}{d+2}}で置き換えると。 x^{2} + y^{2} = 1 + \frac {d-2} {d+2}x^{2}y^{2}
が得られる。

RSA暗号の原理を理解するための数学知識

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

 a = b \mod n, \\
c = d \mod n 

のとき、

 a + c = b + d \mod n

 a * c = b * d \mod n

 a^{m} = b^{m} \mod n

である。

 ef = eg \mod n で gcd(e, n) = 1 ならば
 f = g \mod n
である。

合同式の意味とよく使う6つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、  a^{\phi(n)} = 1 \mod n である。
ここで、gcd は greatest common divider の略で最大公約数を意味する。
 \phi(n) は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 \phi(p) = p-1 となる。

また、p, qが素数の場合、2つをかけた合成数 pq に対して \phi(pq) = (p-1)(q-1)が成り立つ。

RSA暗号の世界 | サルにも分かるRSA暗号

RSAのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
 m = n \mod p
 m = n \mod q
であれば
 m = n \mod pq   である。

中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語