久しぶりのRSA暗号ネタ。RSAで遊ぼうの続き。

OpenSSL RSA暗号の秘密鍵ファイル（private.key）の中に書かれている数字の一部が「exponent1」、「exponent2」、「cofficient」という3つの数字。ここで、
exponent1 = D mod (p-1)、
exponent2 = D mod (q-1)、
coefficient = q^-1 mod p（coefficient*q=1 mod p）、
pとqは公開鍵N=pqの2つの素数pとqで、
Dは復号に使われれる秘密鍵。
「exponent1」、「exponent2」、「cofficient」は中国の剰余定理を使って復号のときの冪剰余計算（M=C^D mod N みたいな計算）を高速に行うためのものだそうだ。

n を法とする冪剰余の計算
k=1024 の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a=b^d mod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (1024bit × 1024bit) を、1500回程繰り返すことで実現できる。 これには相当の計算時間を要するため、中国の剰余定理を用いて、

ap = b^{d mod φ(p)} mod p
aq = b^{d mod φ(q)} mod q
a' = ap(q^-1 mod p)q + aq(p^-1 mod q)p

として求めることがある。

https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7（2021年11月27日閲覧）

だそうで、なぜこれで計算が速くなるのかを確認したいというのが今回の話。

続きを読む →

遊んでいて見かけたツイート。
https://twitter.com/P2_p_q/status/1257238463486717954

114桁の整数を2分ほどで素因数分解？ まじで？

そんな時にはhttp://factordb.com/。
283598282799012588354313727318318100165490374946550831678436461954855068456871761675152071482710347887068874127489 を入れてやると、

2835982827...89<114> = 284111 · 219264419483783<15> · 626353849872486037<18> · 271333108160005173907<21> · 28711987117666459062711317<26> · 932956926264664771198114673851<30>

http://factordb.com/index.php?query=283598282799012588354313727318318100165490374946550831678436461954855068456871761675152071482710347887068874127489

まじ合ってるじゃん。ほんとに2分で暗算？

あることを調べていて見かけたブログの話。
https://ptsv.jp/というブログの「中継サーバーを経由して社内LAN上のテストサーバーへ接続する」という記事なんだが、自宅から社内LANに繋がっているテストサーバーに繋ぐためにSSHポートフォワードを使って実現しましたよという話。

とてもじゃないけど、「VPN設置して家からアクセスさせてください」とか、「ルータのポート一個開けて、俺っちのテストサーバーへルーティングして」とか、そんな都合のいいことが通る(許可される)はずもありません(^^;;;

という環境下でよくそんなことができるなあと、心配するというか呆れるというか怖いというか……

「72の法則」というのは有名だと思う。
利率が r（単位は%）の時、元利合計が2倍になる期間の概算値を求めるには 72 を r で割ればよいというもの。
例えば年利が 5% の時、元利合計が2倍になる期間はだいたい 72÷5=14.4年 ですよ、というもの。

DIAMONDオンラインの「資産を100倍にする超シンプルな数学」という記事には「72の法則」よりももっと精度が高い計算式として「エックハルト＝マクヘイルの二次法則」というのが紹介されていた。

「エックハルト＝マクヘイルの二次法則」というのはいろいろとググってみたのだが、ちゃんとした記述が見つけられなかった。有名な式なのかなあ？

続きを読む →