Rsa

由專家手動破解 RSA(或其他算法)

  • November 14, 2021

RSA 密碼學的強度來自於分解大數的難度(或者我們相信)。對於超過 2048 位的密鑰長度,目前或近期的電腦無法在合理的時間內分解這些數字。

但是人的大腦呢?有些人具有非凡的數學能力;例如,可以執行許多複雜計算的專家。想像一個專注於分解合數的人。也許他或她的能力可以通過藥物來增強。

在設計密碼密碼時,這是一個真正的問題嗎?一個邪惡的組織會僱用其中一個人來破解密碼密鑰(對於任何現代密碼)嗎?也許有一些現實生活中的例子?

心算計算器不會通過盯著輸入來讓結果出現在他們的大腦中。他們遵循一些(大致順序的)算法¹。當電腦使用相同的算法時,它們的性能大大優於它們。對於 1970 年代後期的廉價個人電腦,這已經是至少 100 倍以上。

例如,兩個 8 位數字的 10 次乘法記錄為 162 秒(來源)。即使通過以十進制工作的教科書算法,該任務也需要 640 次涉及 4 個十進制數字的基本運算。具有適當(6502 彙編)程序的[Apple ]將在 1 秒內完成此操作,包括從螢幕“文本”記憶體中提取數字並將結果儲存到螢幕“文本”記憶體中。

我得出的結論是,我們可以完全打折人類神童在破解任何適當的加密貨幣方面的表現優於電腦。


更新:與記錄相同的消息來源在 6'38" 中發現了 20 個隨機五位數複合的因數,這比正確的 RSA 雙素數要容易得多。這說明人腦不擅長因式分解。

更新 2:它也被描述為一個 16(分別為 15、14)位整數的性能因子,該整數已知是四個連續素數的乘積,平均為 23'24"(分別為 13'21"、6'06" ). 我估計蘋果 ][ 即使在十進制下工作時也可以超過 10000 倍,對三個因式分解中的每一個使用費馬方法的一個步驟。


¹ 觀看表演者將兩個 20 位數字相乘為 5'26";世界紀錄為 2'48"。

引用自:https://crypto.stackexchange.com/questions/92167