Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

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

WEBプログラミング

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

/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

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

# crontab -l
00 05 * * * /usr/bin/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の冪乗の値は一つ前で計算した値の２乗になっているので、計算量が最小限に抑えられるのである。

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

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

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

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の変数を一つも使っておらずとても綺麗なロジックになる。