PTT推薦

[爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法

看板Gossiping標題[爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法作者
jackliao1990
(j)
時間推噓推:175 噓:24 →:42

https://eprint.iacr.org/2021/232.pdf

RSA加密法於1977年由Rivest、Shamir和Adleman提出,因為極大數的質因數分解困難度,此方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此一般認為2048位元的密鑰非常安全可靠。

然而德國密碼學家Claus Peter Schnorr在自己新論文摘要中的最後一句宣稱:本文"摧毀"了世界各大機構都在用的RSA加密法。此文一放上網就引起轟動。

如果這篇論文出自無名小卒,大家只會當成笑話。但是這篇作者Claus Peter Schnorr是知名密碼學家,他提出的Schnorr簽章在加密貨幣如比特幣中被廣泛應用,他還是RSA數學卓越獎和萊布尼茲獎得主。

一般認為,我們要等到使用秀爾演算法的量子電腦普及後,RSA加密法才會被破解。然而本文宣稱透過晶格密碼學中的SVP法(尋找最接近向量),即使使用傳統電腦,我們也有機會比二次篩選法和普通數域篩選法(已知最快的傳統因數分解演算法)更快完成分解。

這篇論文目前還未通過同行評審。GitHub上已經有人實作文中的算法,但是沒人成功。也有人指出論文中的可能漏洞:作者宣稱如果使用新算法,"將整數的指數大小加倍"只會讓操作數增加一個數量級。這表示:過去被認為屬於NP問題的操作,被本文證明屬於P,這樣豈不就證明P=NP了?(然而質因數分解從沒被證明是NP完全問題)

--

※ PTT留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.192.157.241 (臺灣)
※ 文章網址: https://www.ptt.cc/Gossiping/M.1618235350.A.604

goldman020404/12 21:49快推~不然人家以為我看不董!!

P556604/12 21:49樓下都直接繞過去

darkbrigher04/12 21:50繞過去

algebraic04/12 21:50跟我昨天睡覺時 神跟我說得差不多

birdy59004/12 21:50數學上其實不太可能~

SRNOB04/12 21:50點點手指 從銀行轉一個兆

play71404/12 21:50我也這樣想

WolfTeacher04/12 21:50恩恩 跟我想的一樣

qk338088804/12 21:50嗯嗯 對

FiveSix91104/12 21:50看不懂 先推 裝一下

yulis04/12 21:50我看幼幼都繞過去就好了啊

calculatortw04/12 21:50Yo叔直接繞過

diabolica04/12 21:50

wonder00704/12 21:51哇 證明NP= P 惹www

ECZEMA04/12 21:51怕~

Neisseria04/12 21:51嫩,yo 叔輕鬆繞

xiaohan04/12 21:51嗯,我也是這樣想

LeafLu04/12 21:52看來還有一段路 沒事兒 還是yo叔厲害

gg889g804/12 21:52THE繞

andy19911304/12 21:52死定了 他會被暗殺

mathrew04/12 21:52跟我想的一樣

wario201404/12 21:53快點先破解比特幣啊,直接弄個三億個灌爆交易所

goldman020404/12 21:53原本我也是這樣想 不過礙於要上班~

Induction04/12 21:53yoyodiy可以告這個人吧?我好幾年前就在用yo叔的程式

Induction04/12 21:53繞過rar密碼了,記得要私信他才會給。

ethan041904/12 21:53果然是這樣

Innofance04/12 21:54RSA真被摧毀銀行還要玩嗎= =

ma4wanderer04/12 21:54都過超過一個月了 鴿子飛到了

shadowdio04/12 21:54所以會怎樣

fp73704/12 21:54住苗栗?

takeda323404/12 21:54 繞過去~~~

R10K04/12 21:54太弱了吧,yo叔都直接繞過去

violegrace04/12 21:54yo叔早就繞過去了

rock080704/12 21:54這個遊戲有必勝法

asiaking556604/12 21:55塊陶阿

darkbrigher04/12 21:55論文都發出來了 暗殺也沒用了

a9403750104/12 21:55我早就想過ㄌ

spfy04/12 21:56現有的加密體系會垮一大半吧

jma30604/12 21:56 我以前不敢公布 因為怕被殺

ljm8704/12 21:56擔心他的未來

yahe052604/12 21:56繞過去就好啦

Vassili24204/12 21:56跟我想的一樣,只是我懶得打成paper

cka04/12 21:57嗯我想也是

lianpig556604/12 21:58之前做專題就有發現了= =

GaussQQ04/12 21:58一堆人出來說那論文有問題了 可以update 最新狀況嗎?

jgj1232104/12 21:58質數的規律就交給你了

Daedolon04/12 22:00p=0或n=1

rodney9204/12 22:00國中在學質因數分解時 就想過了 果然有人跟我一樣解法

kenndy04/12 22:01我高中時就知道了

leamaSTC04/12 22:01終於有其他人想到啦?那我就能省功夫了

saladim04/12 22:02yo叔表示: 還算可以啦 你終於邁出我十年前的第一步啦

s932131204/12 22:03嗯 跟我的解法差不多

goldman020404/12 22:03YO叔幼稚園時候我看他寫這個以為他在開玩笑畫圖~哀!!

butten98604/12 22:05有崩盤啦!

tmwolf04/12 22:06我岳父的筆名比較調皮一點 不好意思

bestrace04/12 22:06幹幹幹快賣比特幣 會被盜光光

Busufu04/12 22:06這理論跟我想的不一樣 應該有漏洞

WeiMinChen04/12 22:06真。密碼學家目前歸隱苗栗深林 這什麼咖

devilkool04/12 22:07證明P=NP....

Tattoo04/12 22:08yoyodiy

poseiden04/12 22:09跟我想的一樣

abadjoke04/12 22:10yoyodiy原來跑到德國去了

suny92104/12 22:12看不懂啦!民進黨惹火我了!

Justin89082004/12 22:12P=NP

honey461791204/12 22:14這念資訊的都看得懂吧==很科普

q456456w04/12 22:18真破了 還不被管制起來 傻吊= =

PompelmousJ04/12 22:22確實 跟我所見略同

BBQ259104/12 22:24768被破解 改2048 再破解 改4096 再改 8192 根本沒鳥用

kite612804/12 22:24三八兄弟 不是我們一起研究的嗎 發表時也不揪一下的欸

linlaosure04/12 22:25好欸

diiky04/12 22:25哇靠,連rsa都不能用了喔

hanklee6604/12 22:25但是沒人成功

abd8673104/12 22:25嗯嗯 我也是這麼想的

richjf04/12 22:26不是很多都改用ecc了?

hannnnnn04/12 22:27先推

dnkofe04/12 22:27快推

amethystboy04/12 22:31yo叔笑而不語

KhePri04/12 22:39太屌了吧

herculus650204/12 22:39差不多是這樣

shadowdio04/12 22:40永樂老師:最近有小朋友問我...

lyt556604/12 22:47yo叔:嫩

mdkn3504/12 22:52∂NP/∂N = P dN

meteor26004/12 22:53P=NP人類直接進化

ashylan04/12 22:54嗯嗯 英雄所見略同

smb101304/12 22:54我都不設密碼

hare103904/12 22:56RSA 總有一天會被解掉,老早就該換 ECC 惹

tom50106200304/12 22:57能破但是要看運算時間吧 不過這個突破的話 世界上的

tom50106200304/12 22:57加密會瘋了

heavenlyken04/12 22:59p=np 人族直接躍遷變神族

lolikung04/12 22:59破了整個世界會瘋掉啊

aisitelu04/12 22:59無聊 要量子電腦才可以 有量子電腦暴力解都行

wrt04/12 23:01樓下的RSA密碼是123456被破解好久了

wrt04/12 23:01裸照已經在網路瘋傳但是沒人看

eDrifter04/12 23:01唉 火星人告訴我的時候 我擔心影響太大沒說 終究被爆出

ll6a04/12 23:01拜託先不說這種不可能破解,誰破了會發論文出來講,又不是

poison556604/12 23:01Np 就可以發一篇超猛的了吧

wrt04/12 23:01改樓樓下

ll6a04/12 23:02傻子0.0..

kei182304/12 23:13早說了就F=MA

j1o2s3e4p5h604/12 23:17比特幣要崩了嗎?

rndsulgye04/12 23:20跟我上個月在思考的問題類似…不過我還不確定,為求謹

rndsulgye04/12 23:20慎先不發表

RicciCurvatu04/12 23:21這種大定理都是大咖詐胡好幾次都是正常的

pr955804/12 23:22yo叔:嫩! 我海放你10年

keyman204/12 23:22世界末日 天國近了

lee98832504/12 23:23no more secret

waloloo04/12 23:24嗯嗯,我都去幼幼稚園繞過去

lpoijk04/12 23:25他漏掉最重要的地方了吧.....

theta471904/12 23:25偷改成錯誤資訊 當然測不出來 最後論文確定了才會改成

theta471904/12 23:25正確資訊 電影都這樣演

pot123404/12 23:32一般來說認為svp比因數分解難很多吧 話說哪邊說到作者覺

pot123404/12 23:32得多項式時間做的完 我看起來他寫的bound是指數啊?

overskyend04/12 23:35沒錯,我老早就這麼認為的

hooll11104/12 23:36又不是只有RSA加密可以用...

ph458604/12 23:38預覽圖勒?

ph458604/12 23:38http://i.imgur.com/TxZsXJg.jpg

圖https://i.imgur.com/TxZsXJg.jpg, [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法

a456785004/12 23:40差不多 跟我想的一樣 只是論文比我早寫好而已

ECZEMA04/12 23:40上個月的事情 拿來批踢踢爆卦 都已經被鞭一回了說

sses6080204/12 23:43恩恩 跟我想的一樣

tatlacz04/12 23:45嗯嗯 我也是這樣覺得

ee8iqp7x04/12 23:48yo叔屌打

willion00304/12 23:48所P=NP確定了嗎?

grec04/12 23:48yo叔早就已經繞過去好久了

unrealstars04/12 23:48繞過就好解個屁

AdamZheng04/12 23:49說的很棒

kkwwee04/12 23:51更快推裝懂

e2ne004/12 23:52這不只虛擬貨幣有影響 你各位用https現在也等於裸體上網

Cireiat04/12 23:54唉,都跟他說不要這麼快submit出去了……多等三天的二次

Cireiat04/12 23:54驗證這麼難嗎?

p7291004/12 23:57rsa被破,aes也不用玩了,所有用數論的密碼學都完了

pilitiger04/12 23:58天堂2m打密碼的時候我就發現了

mojia04/13 00:00沒有一個名詞看得懂的 雖然是中文字

youshallnotp04/13 00:02Yo叔10幾年前就破解了

shortimex04/13 00:04錯誤的證明,得出錯誤的結論,讓我想起1+2+3+4+... =

shortimex04/13 00:04-1/12

xxxrecoil04/13 00:04傻子才破解吧,我們都繞過去

bigsmile504/13 00:07@yo叔

xo110004/13 00:12破解了會先裝死在社會上大開殺戒誰跟你公開

ter278804/13 00:13問題是要多久?

pchunters04/13 00:14蛤,這些不是小學就知道了?

ds36100704/13 00:14等高手解答

h388224904/13 00:14完了 世界要毀滅了

a095286490104/13 00:17加密當然有破解手法 但實務上經常是破完KEY早換了

a095286490104/13 00:17但這新聞用"摧毀"感覺有點太吹了XD

cygnusx12304/13 00:18YO叔笑而不語

slygun04/13 00:18比特幣下去

FinallyPeace04/13 00:18NP=P?太神了吧

xiao2chen04/13 00:21跟我想的一樣

Jokering556604/13 00:21跟我猜得差不多

tmuaircat04/13 00:26YO叔比武招親推動人類文明的錯覺

chiahong122704/13 00:26真的有可能嗎?

Irelia5604/13 00:32某人:學這些數學有什麼用?

nenohelios04/13 00:33如過後段屬實,那他最屌的是解了P=NP欸,這可能嗎

LiaMeow04/13 00:35嗯嗯 我就說吧

marinsky04/13 00:39跟我想的一樣

linja04/13 00:45我竟然都看得懂

sorcxnegi04/13 00:47消息根本不可能出來啦,不是被滅口就是被當國家級武器

sorcxnegi04/13 00:47

linzero04/13 00:49可能是能縮減破解時間,但還是很長吧

linzero04/13 00:50比方原本解要1萬年,變成5千年,這樣嗎?

aarzbrv04/13 00:51質因數分解又沒被證明在NPC裡面。

aarzbrv04/13 00:53第一頁註明work in progress 08.04.2021所以這篇是廣宣喔

cossetannie04/13 01:09終於有人證明P=NP了

ZooseWu04/13 01:09括號裡面自己說不是npc 然後前面說p=np是什麼鬼

yillusionwei04/13 01:11就繞過去理論嘛

aarzbrv04/13 01:14這篇最近版本(4/9)宣稱結果比QS,NFS快很多,但都還沒看到

vasia04/13 01:16他可能是在致敬幼幼

aarzbrv04/13 01:16與先前QS,NFS比較跑出來的實驗結果吧?

Thanksbro04/13 01:16還要破解 我都直接繞過去==

hoo911ver2504/13 01:17我當年學測寫完無聊解出來九成剛好打鐘被收走

※ 編輯: jackliao1990 (123.192.157.241 臺灣), 04/13/2021 01:19:26

haeiou04/13 01:19和我想的不太一樣,建議作者再回去想想

aarzbrv04/13 01:20還有自認為改良的演算法是根據還沒被證出成立的SA假設…

aarzbrv04/13 01:24回p72910:請問AES何時基於RSA?兩個系統差很多耶

a00052200104/13 01:30快推 不然以為我看不懂

aarzbrv04/13 01:36所以請教樓上發現哪些具體突破呢?

vimer04/13 01:39是喔 阿不就好棒棒

danny40985904/13 01:49推,優質好文

joemi7804/13 01:54好像離散學過欸

RLH04/13 01:55看不懂

rickyshiter04/13 02:00我早就摧毀了

tn60137404/13 02:12yoyodiy快點拿專利吉他

daye8704/13 02:17有生之年能看到p=np無憾

ymx3xc04/13 02:30yo叔能繞過RSA 4096

EvilJustice04/13 02:392048不夠再加阿,4096,8192?

rnmrn04/13 02:44我以為大家都知道

iewix04/13 02:58yo叔已經繞過多少年了

llrabel04/13 03:06看到這種驚天大發現,直接賭他證錯就對了

whatzup112404/13 03:12NP hArd

jasonchangki04/13 03:23有人照論文實作但沒成功很大機率出事了吧

HHH555JJJ04/13 03:52P=NP?Turin award 得主出現了

s1235897204/13 04:40也就是說,這篇論文被實作出來還能順便證明P=Np

gamania025804/13 04:52RSA可以被破解該拿圖靈 證明N=NP有更高的榮譽可以頒

gamania025804/13 04:52

s1235897204/13 04:56諾貝爾吧

orze0404/13 05:36真的證明P=NP要拿自己的名字當獎都可以了

rs600004/13 05:44等李永樂 拍片來解答...

xacid04/13 05:49推 yo 叔

TenGaKu180904/13 06:06他如果證明NP=P 他會創另一個諾貝爾獎XD

arue04/13 06:06也來裝懂一下

DarkHolbach04/13 06:10德國yo叔

ewjfd04/13 06:17的確如此

sanpf04/13 06:24YO叔早就破解了

oxlittle04/13 06:36看到第一頁就放棄了= =

REDF04/13 06:38菜雞問問yo叔是什麼

chichiliou7704/13 07:12跟我想的一模一樣

f41672000104/13 07:19看到離散,我頭髮又掉了兩根

srena04/13 07:19嗯...長了關於yoyodiy的知識

willy020604/13 07:28p=np 我到底看了什麼

j0724205404/13 07:35繞過去就好了啦 yo叔有教

aaron6803204/13 07:42快破解比特幣讓他崩到沒價值 我想看賤畜礦工跳樓

loveadu04/13 07:48這我早就知道了

shirleyEchi04/13 08:03這點問題高中就提過只是沒有深究而已 德國人還真閒

asidy04/13 08:06乾,看不懂,我要繞過去了

kukuyo04/13 08:07跟我想的一樣

seio200804/13 08:08跟我想的差不多

nevillechao04/13 08:19應該是只要不是真NP問題,就只是P問題。而非P=NP

Silwez04/13 08:51可是SVP本身也沒有polynomial time的演算法

space2002104/13 09:27yoyodiy可以繞過

cloud103004/13 09:44P=NP 的前題是N必為1,小心惹

deray04/13 10:25跟我想的一樣 只是我懶得寫論文

kirisame04/13 10:26就看不懂 裝屁

qxpbyd04/13 11:143月初就有的舊聞

qxpbyd04/13 11:20https://is.gd/wPTqay

steven83031904/13 11:32我也是這樣想的

wei989804/13 12:02量子加密法要登場了嗎

hanmas04/13 12:08SVP比factoring難多了吧 reduce到SVP是想怎樣

joy2588137104/13 12:19我也這樣覺得

BENNY4904/13 13:51嗯嗯嗯 喔喔

apple12377304/13 14:25有yoyo叔那麼厲害嗎?

gay778804/13 15:01yo叔早就繞過了,發現世界沒有對手才回家種田的

a882403104/13 15:08我們台灣早就有人直接繞過去了

ewjfd04/13 16:23p=np 我更傾向寫成Ⓟ=Np~*.★ 增加活潑感

CTUST04/13 17:59不懂 量子電腦有辦法解決嗎?

james8035104/13 20:42量子電腦差在qubit數還不夠多啊

fongshing04/13 20:48可惜慢了一步 也好 成功不必在我

aarzbrv04/13 22:03請問目前有聽說哪家公司有量子電腦產品呀

aarzbrv04/13 22:18請問樓上有哪些人日常生活有需要用到RSA加密法保護自己的

aarzbrv04/13 22:20資料的?如果完全沒有那就算今天RSA變得很好破,應該不會

aarzbrv04/13 22:20因此造成晚上無法入睡吧?

wattswatts04/14 00:27金融體系加密。。。。

zebraseven04/14 11:27Push