RSA-240 が解けたらしい

no extension

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 20091, and a 768-bit prime discrete logarithm in June 20162.

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


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

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

via 795-bit factoring and discrete logarithms

だそうな

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

ちなみに,セキュリティ強度と鍵長の関係は以下の表の通り(単位は全て bit)。

Security
Strength
Symmetric
key
algorithms
FFC
(e.g., DSA, D-H)
IFC
(e.g., RSA)
ECC
(e.g., ECDSA)
$\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 strengths (via SP800-57 Part 1 Revision 4 )

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

Security Strength Through
2030
2031 and
Beyond
$\lt 112$Applying Disallowed
ProcessingLegacy-use
$112$ Applying AcceptableDisallowed
Processing Legacy use
$128$ Applying/ProcessingAcceptableAcceptable
$192$ AcceptableAcceptable
$256$ AcceptableAcceptable
Security-strength time frames (via SP800-57 Part 1 Revision 4 )

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

ブックマーク

参考図書

photo
暗号技術入門 第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)

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

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

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