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分で暗算?

Windowsインストール用のISOファイルからOSのバージョンを調べたい

OSインストール用のISOイメージに含まれるWindows OSのバージョン/エディション/ビルド番号などの情報を調べる

ISOファイルからinstall.wimあるいはinstall.esdを抽出(sourcesディレクトリーあたり)
コマンドプロンプトを管理者として実行して、

dism /get-wiminfo /wimfile:install.win
dism /get-wiminfo /wimfile:install.win /index:1

などとする。

ブログを読んでいて心配になった話

あることを調べていて見かけたブログの話。
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

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

続きを読む

仮想CentOSでswapをLVMから仮想HDDに変更

VMwareで動かしている仮想CentOS6で、swapをLVMから仮想HDDに変更したときのメモ。
grubの変更を忘れると立ち上がらなくなるので注意。(なお、立ち上がらなくなってしまった場合には、grubの起動画面でeを押して起動オプションを変更して回避)

手順の流れは、以下の通り。

VMwareで新規の仮想HDDを一つ作成(例えば/dev/sdb)
仮想CentOS起動
swapをオフ
swapのLogicalVolumeを削除(例えば/dev/vg_localhost/lv_swap)
fdiskで/dev/sdbにswapの領域を作成(/dev/sdb1。パーティションの種類を82(Linux swap)に変更するのを忘れずに)
mkswapでswap領域を作成
/etc/fstabを編集して、LVMのswapを使わずに/dev/sdb1を使うように変更
swapをオンにして、freeとか/proc/swapsで確認
/boot/grub/grub.cfgを編集(「rd_LVM_LV=vg_localhost/lv_swap」なんて感じのところを削除)

コマンドだけ並べて書くとこんな感じ。

sudo su
swapoff -a
lvremove /dev/vg_localhost/lv_swap
fdisk /dev/sdb
mkswap /dev/sdb1
vi /etc/fstab
swapon -a
free
cat /proc/swaps
vi /boot/grub/grub.cfg

CentOS7とかだと、grub.cfgを直接変更するのではなくて、

vi /etc/default/grub
grub2-mkconfig -o /boot/grub2/grub.cfg

のようになるはず。(確かめていない)

「私の恋で死んでくれ」


prtimes.jpの素材より)

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

続きを読む