RSA-240 が解けたらしい

“RSA-240 Factored - Schneier on Security” 経由：

RSA challenge list のうち RSA-240 が解けたようだ。

We are pleased to announce the factorization of RSA-240, from RSA's challenge
list, and the computation of a discrete logarithm of the same size (795 bits):

RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
        = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517
        * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

[...]

The sum of the computation time for both records is roughly 4000
core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz).
A rough breakdown of the time spent in the main computation steps is as
follows.
    RSA-240 sieving:  800 physical core-years
    RSA-240 matrix:   100 physical core-years
    DLP-240 sieving: 2400 physical core-years
    DLP-240 matrix:   700 physical core-years

795-bit factoring and discrete logarithms

なお

The previous records were RSA-768 (768 bits) in December 2009¹, and a 768-bit prime discrete logarithm in June 2016².

It is the first time that two records for integer factorization and discrete logarithm are broken together, moreover with the same hardware and software.

https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt ↩︎

https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;a0c66b63.1606 ↩︎

via 795-bit factoring and discrete logarithms

だそうな

まぁ，クラウド等を使った安価な分散コンピューティングや実用化されつつある量子コンピュータの台頭により，これから状況は変わっていくだろうけど一応の指標にはなると思う。

ちなみに，セキュリティ強度と鍵長の関係は以下の表の通り（単位は全てビット）。

Security Strength	Symmetric key algorithms	FFC (DSA, DH, MQV)	IFC (RSA)	ECC (ECDSA, EdDSA, DH, MQV)
$\le 80$	2TDEA	$L=1024$ $N=160$	$k=1024$	$f = 160\text{ - }223$
$112$	3TDEA	$L=2048$ $N=224$	$k=2048$	$f = 224\text{ - }255$
$128$	AES-128	$L=3072$ $N=256$	$k=3072$	$f = 256\text{ - }383$
$192$	AES-192	$L=7680$ $N=384$	$k=7680$	$f = 384\text{ - }511$
$256$	AES-256	$L=15360$ $N=512$	$k=15360$	$f=512+$

Comparable security strengths of symmetric block cipher and asymmetric-key algorithms (via SP 800-57 Part 1 Revision 5 5.6.1.1)

更に各セキュリティ強度の有効期限は以下のとおりだ。

Security Strength		Through 2030	2031 and Beyond
$\lt 112$	Applying	Disallowed
$\lt 112$	Processing	Legacy use
$112$	Applying	Acceptable	Disallowed
$112$	Processing	Acceptable	Legacy use
$128$	Applying/Processing	Acceptable	Acceptable
$192$		Acceptable	Acceptable
$256$		Acceptable	Acceptable

Security-strength time frames (via SP 800-57 Part 1 Revision 5 5.6.3)

まぁ今どき1,024ビット以下の鍵長で運用している馬鹿者はおらんじゃろうけど，2030年以降を見据えるならそろそろ RSA や ElGamal/DSA 等の古い公開鍵暗号について見直しを始めるべきなんだろうね。

ブックマーク

暗号鍵関連の各種変数について

参考図書

暗号技術入門第3版　秘密の国のアリス: 結城浩 (著); SBクリエイティブ 2015-08-25 (Release 2015-09-17); Kindle版; B015643CPE (ASIN); 評価

SHA-3 や Bitcoin/Blockchain など新しい知見や技術要素を大幅追加。暗号技術を使うだけならこれ1冊でとりあえず無問題。

reviewed by Spiegel on 2015-09-20 (powered by PA-APIv5)

暗号化プライバシーを救った反乱者たち: スティーブン・レビー (著), 斉藤隆央 (翻訳); 紀伊國屋書店 2002-02-16; 単行本; 4314009071 (ASIN), 9784314009072 (EAN), 4314009071 (ISBN); 評価

20世紀末，暗号技術の世界で何があったのか。知りたかったらこちらを読むべし！