素数の音楽を読みました。(その２）

(格子: Latticeの例）

前回は、最近読んだマーカス デュ・ソートイ の「素数の音楽 (新潮文庫)」に書かれていたリーマン予想について書きましたが、この本には、インターネットで利用されているRSA（Rivest–Shamir–Adleman：発明者3人の名前）暗号の誕生や、RSA129 の解読には、4京年かかると思って懸賞金をかけたら、レンストラとマナッスによって1994年に解かれてしまった話なども書かれています。

RSA129とレンストラ博士の話は、当時のThe New York Times の記事にもなっています。（タイトルが長い）
The Assault on 114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,271,242,362,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541

https://www.nytimes.com/1994/03/22/science/assault.html

コンピュータの性能が高くなったことと、効率の良い計算方法が発見されたことで、暗号の強度を保つためには、桁数の多いより複雑な鍵を使わなければならなくなって、現在では2048ビット以上の長さが推奨されていますが、この先さらに効率の良いプログラムや量子コンピュータができてしまたときのために、米国国立標準技術研究所（NIST）を中心に耐量子計算機暗号（PQC: Post-quantum cryptography）という新しい暗号化の標準を決めようとしているそうです。（もうすぐ決まる）
https://csrc.nist.gov/Projects/post-quantum-cryptography


（ちょっと古い資料だけど、絵がかわいいので：https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/asiacrypt-2017-moody-pqc.pdf
THE SHIP HAS SAILED The NIST Post-Quantum Crypto “Competition”Dustin Moody, NIST )

レンストラ博士が考えたRSAへのアタックは、レンストラ–レンストラ–ロヴァッツの格子基底縮小アルゴリズム(Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm)という計算方法を利用するもので、UCSDなどでは学部の授業でやるみたいです。(200番台なので2年生？）
https://cse.ucsd.edu/graduate/current-quarter-course-descriptions-recommended-preparation


全くヒントがない暗号文だと、パソコンでは1年かけても計算できませんが、短い文章や、文章の一部分がわかっていると、ノートパソコンでも一瞬で計算できます。
UCSDの CSE 291-I: Applied Cryptography Nadia Heninger UCSD Spring 2020 Lecture 17
https://cseweb.ucsd.edu/classes/sp20/cse291-i/lectures/17-lattices-notes.pdf
にSage Mathで計算する例があったので、自分のノートパソコンでやってみました。

---
N=random_prime(2^150)*random_prime(2^150)
message = Integer('thepasswordfortodayisswordfish' , base=35)
c=message^3%N

# 'thepasswordfortodayis’ まで分かっていてパスワードが謎の場合
a=Integer('thepasswordfortodayis000000000' ,base=35)
X=Integer('xxxxxxxxx' ,base=35)
M=matrix([[X^3,3*X^2*a,3*X*a^2,a^3-c], [0,N*X^2,0,0],[0,0,N*X,0],[0,0,0,N]])

#　LLL格子基底縮小
%time
B=M.LLL()
Q=B[0][0]*x^3/X^3+B[0][1]*x^2/X^2+B[0][2]*x/X+B[0][3]
Q.roots(ring=ZZ)[0][0].str(base=35)

# CPU times: user 0 ns, sys: 0 ns, total: 0 ns
# Wall time: 3.34 µs

# 解読結果
# 'swordfish'

ちなみに、パスワードの例’swordfish'は、ハッカーが主人公の映画のタイトルで、映画の中で「最もハッキングされにくいコンピュータは何か知っているか？DECのコンピュータだ、なぜなら使っている人が少ないから」みたいな会話があって、私はDECに勤めていたので、ちょっと複雑な気持ちでした。

---

リーマンのゼータ関数の複素平面のプロット、英語版のWiki
https://en.wikipedia.org/wiki/Riemann_zeta_function
にかっこいいのがあったので、真似してみました。
たぶん
https://github.com/davidlowryduda/phase_mag_plot
を使っているんじゃないかな？