RSA破解作業(yè)

截至:11月07日23:59提交作業(yè)

Alice decides to use RSA with the public key N = 1889570071. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent e1 = 1021763679 and once using the encryption exponent e2 = 519424709. Eve intercepts the two encrypted messages

c1 = 1244183534 and c2 = 732959706. Assuming that Eve also knows N and the two encryption exponents e1 and e2. Please help Eve recover Bob’s plaintext without finding a factorization of N.

選做力崇,交電子版,寫成md文檔,交鏈接颖御。提示:簡單題寓落,不同于共用模數(shù)攻擊纠俭。

公匙N=1889570071雳锋,加密指數(shù)e1 = 1021763679颂砸,e2 = 519424709

密文c1 = 1244183534灶轰,c2 = 732959706

首先假設(shè)谣沸,e1,e2互質(zhì)

即gcd(e1,e2)=1

此時(shí)有e1*s1+e2*s2 = 1

式中笋颤,s1乳附、s2皆為整數(shù),但是一正一負(fù)伴澄。

通過擴(kuò)展歐幾里德算法赋除,我們可以得到該式子的一組解(s1,s2),假設(shè)s1為正數(shù),s2為負(fù)數(shù).

因?yàn)?/p>

c1 = m^e1%n

c2 = m^e2%n

所以

(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n

根據(jù)模運(yùn)算性質(zhì)非凌,化簡

(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n

(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n

又因?yàn)?/p>

e1*s1+e2*s2 = 1

所以

(c1^s1*c2^s2)%n = (m^(1))%n

(c1^s1*c2^s2)%n = m^%n

c1^s1*c2^s2 = m

代碼:

#!/usr/bin/python

#coding=utf-8

def egcd(a, b):

if a == 0:

return (b, 0, 1)

else:

g, y, x = egcd(b % a, a)

return (g, x - (b // a) * y, y)

def modinv(a, m):

g, x, y = egcd(a, m)

if g != 1:

raise Exception('modular inverse does not exist')

else:

return x % m

def main():

n = int(1889570071)

c1 = int(1244183534)

c2 = int(732959706)

e1 = int(1021763679)

e2 = int(519424709)

s = egcd(e1, e2)

s1 = s[1]

s2 = s[2]

#求模反元素

if s1<0:

s1 = - s1

c1 = modinv(c1, n)

elif s2<0:

s2 = - s2

c2 = modinv(c2, n)

m = (pow(c1,s1,n)*pow(c2,s2,n))%n

print (m)

if __name__ == '__main__':

main()

所以举农,最后答案是1054592380

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市敞嗡,隨后出現(xiàn)的幾起案子颁糟,更是在濱河造成了極大的恐慌,老刑警劉巖喉悴,帶你破解...
    沈念sama閱讀 216,843評(píng)論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件棱貌,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡箕肃,警方通過查閱死者的電腦和手機(jī)婚脱,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,538評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來勺像,“玉大人起惕,你說我怎么就攤上這事∮缴荆” “怎么了惹想?”我有些...
    開封第一講書人閱讀 163,187評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長督函。 經(jīng)常有香客問我嘀粱,道長激挪,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,264評(píng)論 1 292
  • 正文 為了忘掉前任锋叨,我火速辦了婚禮垄分,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘娃磺。我一直安慰自己薄湿,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,289評(píng)論 6 390
  • 文/花漫 我一把揭開白布偷卧。 她就那樣靜靜地躺著豺瘤,像睡著了一般。 火紅的嫁衣襯著肌膚如雪听诸。 梳的紋絲不亂的頭發(fā)上坐求,一...
    開封第一講書人閱讀 51,231評(píng)論 1 299
  • 那天,我揣著相機(jī)與錄音晌梨,去河邊找鬼桥嗤。 笑死,一個(gè)胖子當(dāng)著我的面吹牛仔蝌,可吹牛的內(nèi)容都是我干的泛领。 我是一名探鬼主播,決...
    沈念sama閱讀 40,116評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼敛惊,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼师逸!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起豆混,我...
    開封第一講書人閱讀 38,945評(píng)論 0 275
  • 序言:老撾萬榮一對(duì)情侶失蹤篓像,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后皿伺,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體员辩,經(jīng)...
    沈念sama閱讀 45,367評(píng)論 1 313
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,581評(píng)論 2 333
  • 正文 我和宋清朗相戀三年鸵鸥,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了奠滑。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,754評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡妒穴,死狀恐怖宋税,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情讼油,我是刑警寧澤杰赛,帶...
    沈念sama閱讀 35,458評(píng)論 5 344
  • 正文 年R本政府宣布,位于F島的核電站矮台,受9級(jí)特大地震影響乏屯,放射性物質(zhì)發(fā)生泄漏根时。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,068評(píng)論 3 327
  • 文/蒙蒙 一辰晕、第九天 我趴在偏房一處隱蔽的房頂上張望蛤迎。 院中可真熱鬧,春花似錦含友、人聲如沸替裆。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,692評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽辆童。三九已至,卻和暖如春南缓,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背荧呐。 一陣腳步聲響...
    開封第一講書人閱讀 32,842評(píng)論 1 269
  • 我被黑心中介騙來泰國打工汉形, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人倍阐。 一個(gè)月前我還...
    沈念sama閱讀 47,797評(píng)論 2 369
  • 正文 我出身青樓概疆,卻偏偏與公主長得像,于是被迫代替她去往敵國和親峰搪。 傳聞我的和親對(duì)象是個(gè)殘疾皇子岔冀,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,654評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容