RSA暗号と中国の剰余定理と冪剰余計算の高速化

久しぶりの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=CD mod N みたいな計算)を高速に行うためのものだそうだ。

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

ap = bd mod φ(p) mod p
aq = bd 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日閲覧)

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

続きを読む

素因数分解世界1位の人

遊んでいて見かけたツイート。
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設置して家からアクセスさせてください」とか、「ルータのポート一個開けて、俺っちのテストサーバーへルーティングして」とか、そんな都合のいいことが通る(許可される)はずもありません(^^;;;

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

預金が2倍になる期間

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

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

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

続きを読む

台風が大きいほど、台風の勢力が強くなると思いますか?

【誤解②】「台風の大きさ」=「台風の勢力」ではない?

台風の指標の中には「大きさ」と「強さ」があります。アンケートで「台風が大きいほど、台風の勢力が強くなると思いますか (単一回答)」と質問をしたところ、半数以上の方が「そう思う」と回答しました。

気象庁は、台風の「大きさ」を「強風域 (平均風速が15m/s以上の風が吹いているか、吹く可能性がある範囲)」で、台風の「強さ」を「最大風速」でそれぞれ区分しています。台風が大きいほど強風域の範囲は広くなるため、被害は広範囲に及びやすくなります。ですから、大きい台風が日本に接近しているときは、今いる場所が台風の中心から離れていたとしても、注意・警戒が必要になります。

甚大な被害をもたらした比較的小さな台風 2019年台風15号

ただ、台風大きいほど、台風の勢力が強くなるというわけでもありません。

https://news.yahoo.co.jp/articles/f3f96661c6154611eb08e9c663196cb9ab67c4fd

「台風が大きいほど、台風の勢力が強くなると思いますか?」という設問にモヤモヤしてしまった。

続きを読む

「私の恋で死んでくれ」


prtimes.jpの素材より)

としきさんはインディーズ漫画家。ジャンプルーキー!の「もえラんド!」を読んでファンになった。
さて、としきさんの「編集者注意報」という作品があるのだが、クスナさんという漫画家が編集者(あるいは出版社)に作品をパクられる(パクられそうになる)ストーリである。この中で、最初は「原案:クスナ」と表示されていたのが、絵を描く人との連名に変わったりして、最終的には「原作:クスナ」になった、という流れになっている。
気になったのでググってみた。

続きを読む

楽天回線エリアは本当にあったんだ!

全然繋がらない楽天回線だったが、おっきな街だと繋がった。
となるとエリアマップを信じちゃだめということなんだろうね。想像すると、電波の強さは基準値に達しているが、繋がるとは言ってない、というような感じなんだろうか。それって楽天回線を使ってデータ無制限希望の人にとっては重要だよねえ(パートナーエリアだと月5GBまでは高速だが、それ以上は低速(といっても1Mbpsらしいが)になる)。そのあたりのチェックも含めての3か月無料なんだろうね。

楽天モバイル自社回線に繋がらない

楽天モバイルのサービスエリアマップを見て、ここなら自社回線に繋がるだろうという場所、それも屋外で試してみた。
再起動、機内モードOnOFF、モバイルデータ通信OnOffなどを試してみたが、いくら試しても、何度試しても常に「パートナー回線エリア接続中」となってしまった。
楽天の自社回線というのは幻なのか?
1GB以上使う予定はないので実害は全くないのだが、やっぱり気になる。