日常生活的資訊安全 修平科技大學-資訊處-黃志雄.

Presentation on theme: "日常生活的資訊安全 修平科技大學-資訊處-黃志雄."— Presentation transcript:

1 日常生活的資訊安全 修平科技大學-資訊處-黃志雄

2 大綱 Enigma與二次世界大戰 基礎密碼學 進階密碼學

3 二次世界大戰 二戰爆發，同盟國與軸心國互相抗衡 大西洋攸關英國存亡 美國反攻歐洲據點—英國 美國運送物資依靠大西洋

4 二次世界大戰 1939年，德軍採 U-boat 潛艇，搭配密碼機 Enigma 作戰， 使英美飽受威脅
1941 Apr~Jun，德軍摧毀英美船數為英美製造船數之三倍

5 二次世界大戰 為破解德國 Enigma，英美實行破解行動—Ultra (英國情報分級：Ultra, Pearl, Thumb)
由Bletchley Park裡的Alan Turing破解 Enigma 拯救超過三百艘以上船隻

6 Enigma 歷史(1/2) 1918年，由德國發明家 Arthur Scherbius發明 1926年，德軍正式購入
陸續生產超過 100,000部 二戰德軍訊息均以此加密傳輸 Arthur Scherbius

7 Enigma 歷史(2/2) 一戰後，英國仍持續監聽德國通訊 1926年後，Enigma上場，英、法完全無法得知德國訊息
1939年，二戰爆發 Enigma破解—二次世界大戰關鍵

8 Enigma 原理(訊息未加密) ABC .- -... -.-. ABC 訊息 Morse code 訊息 ABC 攔截並解碼
encode decode ABC ABC 訊息 Morse code 訊息 ABC 攔截並解碼 Morse code sounder

9 摩斯電碼(Morse code) . 短音 - 長音 A .- B -... C -.-. D -.. E . F ..-. G --.
H   .... I   .. J   .--- K   -.- L   .-.. M   -- N   -. O   --- P   .--. Q   --.- R   .-. S   ... T   - U   ..- V   ...- W   .-- X   -..- Y   -.-- Z   --.. 0   ----- 1   .---- 2   ..--- 3   ...-- 4   ....- 5   ..... 6   -.... 7   --... 8   ---.. 9   ----. . 短音 - 長音

10 Enigma 原理(訊息已加密) ABC KQX -.- --.- -..- 明文 密文 Morse code Enigma加密 ABC
encode ABC KQX 明文 密文 Morse code Enigma加密 decode ABC KQX 明文 密文 Enigma解密

11 Enigma 構造 反射器(Reflector) 滾輪(rotor) 燈泡(lamp) 按鍵(keyboard)
接線板(stecker, plug board)

12 運作方式

13 運作方式

14 接線板 用電線將兩個字母對調

15 接線板

16 滾輪 用以將明文打亂 類似電表，按一鍵後，最右邊滾輪轉一格 由右邊帶動左邊

17 滾輪 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z In: Rotor I
Out: E K M F L G D Q V Z N T O W Y H X U S P A I B R C J In: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Rotor II Out: A J D K S I R U X B L H W T M C Q G Z N P Y F V O E In: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Rotor III Out: B D F H J L C P R T X V Z N Y E I W G A K M U S Q O In: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Reflector Out: Y R U H Q S L D P X N G O K M I E B F Z C W V J A T

18 滾輪

19 滾輪

20 滾輪

21 Enigma 圖集 2001年在美國東岸失事潛艇尋獲的Enigma

22 Enigma 圖集 上頁經清洗的結果

23 Enigma 圖集 2002年發現於美國東岸的Enigma

24 Enigma 圖集 經清洗之後，較為完整

25 Enigma 圖集 機件亦非常完整

26 Enigma 圖集 製於1944年，德軍懷疑 3-rotor的Enigma被破解， 因此製造4-rotor Enigma

27 Enigma 圖集 上蓋，保留備用燈泡、過濾 板、兩條電線及說明指示

28 Enigma 圖集 說明指示、兩條備用電線及序號牌

29 Enigma 圖集 上蓋的說明指示

30 Enigma 圖集 Enigma上觀圖

31 Enigma 圖集 面板、按鍵、滾輪、顯示燈

32 Enigma 圖集 軍事識別標籤

33 Enigma 圖集 燈泡上蓋移除圖

34 Enigma 圖集 Plug-board近照

35 Enigma 圖集 Plug-board近照

36 Enigma 圖集 滾輪設定區

37 Enigma 圖集 全部面板移除後

38 Enigma 圖集 滾輪近拍

39 Enigma 圖集 滾輪及輪軸拆除後

40 Enigma 圖集 反射器轉輪(reflector)移除後

41 Enigma 圖集

42 Enigma 圖集

43 Enigma 圖集

44 滾輪內部

45 密碼本

46 密碼本

47 Enigma 安全分析(1/2) Plug-board最多可接13條電線
若接0~6條電線，將產生105,578,918,576=10¹¹ 種可能 3個滾輪之位置將3!=6種組合，加上滾輪之初始字 母位置 263，共為105,456種可能 故有105,578,918,576 X 105,456 =11,133,930,437,350,656 (約1016)種可能的設定

48 Enigma 安全分析(2/2) 加上以下變化 反射器種類 滾輪上Ringsettings設定 Enigma可能設定數可達1023

49 破解Enigma 獵殺U-571 (2000年) 聯軍獲勝應歸功於破解Enigma之數學家們 此劇情純為虛構

50 竊取Enigma事蹟 1941年5月9日，由Joe船長佔領德軍 U-110，並取走船上的 Enigma
Captain Joe Baker-Cresswell ( )

51 竊取Enigma事蹟 I still wake up at night fifty-six years later to find myself going down that ladder. David Balme

52 Enigma電影 中譯：攔截密碼戰

53 波蘭嚐試破解Enigma 早在1932年，波蘭便開始研究Enigma如何破解
Marian Rejewski等人已可破解Enigma，並製造 Bomba 加快破解速度 Henryk Zygalski Marian Rejewski Jerzy Rozycki

54 Bomba

55 Initial code breaker – Marian Rejewski
德軍將 DAY KEY 加密兩次，並放在密文前面 如：當天密碼本規定起始位置為ABC 加密者隨選三個字母CIL，以ABC起始，對CIL加密兩次，可得到FMHYUJ 解密者以ABC起始，對FMHYUJ解密，得到CILCIL，則CIL為此篇訊息的Key

56 Initial code breaker – Marian Rejewski
德軍將金鑰藏在前2組的3碼字母中 搜集更多密文，可得到許多金鑰組 DMQ VBN QBLTW LDAHH YEOEF PTWYB LENDP MKOXL DFAMU DWIJD XRJZ PUC FMQ VON PUY DMQ VBN

57 Initial code breaker – Marian Rejewski
將第1個字母及第4個字母相連 攔截的密文夠多，將可得到完整對應 (DVPFKXGZYOD)(EIJMUNQLHT)(BC)(RW)(A)(S) 尚未看過Enigma長成怎樣，便能得知金鑰特徵 第1、4個字母： (10, 10, 2, 2, 1, 1) 第2、5個字母： (9, 9, 3, 3, 1, 1,) 第3、6個字母： (13, 13) DV VP PF FK KX XG GZ ZY YO OD

58 Initial code breaker – Marian Rejewski
滾輪共有3! X 263 = 種可能設定，Rejewski將各種 設定的特徵詳列在他的目錄中 再依今日的「特徵」與目錄本中比對，便可知當日滾輪的 順序與字母初始位置設定 便能解開今日的密文

59 波蘭Biuro Szyfrow密碼局解散 1939年，波蘭密碼局因德國改變重複密鑰輸入方式且經 費不足，不再解密德軍密文
德軍入侵波蘭後，波蘭便將密碼破解技術轉移給英國、法 國

60 Bletchley Park 二戰爆發後，Bletchley Park成為同盟國最大破解 Enigma 的機構
位於London北方80公里處的私宅 1938年英國接收為 Government Code & Cypher School 今已開放為博物館

61 Bletchley Park

62 Alan Turing Alan Mathison Turing, 1912~1954 英國數學家

63 Alan Turing Turing先大量搜集歷史訊息並分析密文 發現密文有固定結構 可由訊息發送時間和來源，預測訊息內容
每天早上6點，德國將發出加密的氣象訊息 訊息必有 “wetter” 字眼 此為破解之線索

64 破解Enigma Turing在心中想像三台Enigma 第一台滾輪設為S 第二台滾輪設為S+1 第三台滾輪設為S+3 滾輪設定 S S+1
猜測明文 w e t t e r E T J W P X 密文

65 破解Enigma E w e T t W

66 破解Enigma 可由1016縮成60*263= 種可能機會 60種滾輪排列方式 263種字母初始位置

67 破解Enigma 將此 種可能性，交由機器暴力破解，一一測試， 如燈泡一亮，便能得知滾輪位置及字母起始位置

68 Bombe

69 德軍成敗—Enigma 由於使用Enigma，德軍茁狀迅速 而Hitler與德軍的戰敗，則是太過相信Enigma

70 Enigma 模擬器練習 請下載： 試解密： 題別 密碼 接線 滾輪順序 滾輪微調 滾輪初始位置 1 QXF JI RSXC VWBR GZ GPNTC O-R B-L Y-Z 4-5-1 1 4 25 G Q P 2 FBWVSZX RRZQJ PPAQHY BQUP HFYWW G-Q W-P T-X 2 3 1 15 5 3 A Q P 3 UNF ILSRM OJWA XD UUBC U-I M-A N-G 1 3 5 1 2 3 Z B W 4 C BFA IKJ WGLS IY V NHTW B-L A-V E-H U-N 3-2-1 R O X 5 Q XTTN OTUIIV DW VFTF JVGRHKGGR H-S I-U P-N 3 5 19 X C Y 6 WFQHXJ XRCW ALNS EMWHPL MM UXVBW TWJZKG L-H W-X M-N 5 4 3 U B Z 7 GIF ZI PTGK LPDM UAMW QKBJ X-Y H-P B-L 3 2 1 M O W 8 R THSVUP TE CMUM DH D CUNSHN RYEYRP E-X H-Y T-Z 2 5 3 2 15 8 U G W 9 F XEZWIC HE AUXJ XMWFK QDLT V-A X-I N-U 5 3 1 10 8 3 R P Q 10 F TBX HTVFO VYCQSD OSIIX CQKP I-V X-U K-J 4 1 2 1 8 18 Z M Y

71 對稱式加密系統 使用同一種演算法及金鑰進行加密、解密 加密 演算法及金鑰 演算法及金鑰 以密文傳輸 解密 明文 明文

72 對稱式加密系統 P 為明文(Plaintext)訊息 K 為金鑰(Key) E 為加密演算法(Encrypt algorithm)
加密程序 C = EK(P) P 為明文(Plaintext)訊息 K 為金鑰(Key) E 為加密演算法(Encrypt algorithm) C 為密文(Ciphertext) 解密程序 P = DK(C) D 為解密演算法(Decrypt algorithm)

73 對稱式加密系統 加解密演算法原則 取代(substitution)：將明文中的每個元素，對應到另一個元素(如一個位元、字母)
置換(transposition)：將明文中的元素重新排列

74 計算上的安全 計算上的安全(Computationally secure) 破解密文所需成本 > 密文本身價值
破解密文所需時間 > 訊息有效壽命

75 暴力破解 逐一嚐試可能的金鑰 如學生Email密碼僅設成數字四位數 猜測：0000~9999 最大猜測數：10000次
每秒猜測10次，需10000/10秒 約17分鐘內便能破解

76 暴力破解 金鑰長度 (bit) 可能的金鑰數 費時 每微秒測試一次 32 232=4.3*109 2.15毫秒 56 256=7.2*1016 10.01小時 128 2128=3.4*1038 5.4*1018年 秒=1000毫秒= 微秒

77 古典加密技術

78 埃及象形文字 西元前19世紀，埃及人將象形文字寫在各處以聯絡族人

79 埃及象形文字 因此埃及象形文字乃是我們有知以來最早的加密系統

80 舊約聖經 西元前5世紀，Adbash密文轉換成希伯來文 使用 “替換” 方式加解密 “HSIUPING”  “SHRFKRMT”

81 斯巴達加密 西元前5世紀，於希臘斯巴達，使用一種名為 “Scytale” 的權仗，並將長條皮革寫上訊息，捲在權仗上便能解密。

82 Polybius Square Polybius (201BC~120BC)希臘人，發明一 5 x 5 方格加密，將字母轉換成數字。 1 2
先取得列號，再取得欄號 “TAIWAN”  “ ” 1 2 3 4 5 A B C D E F G H I/J K L M N O P Q R S T U V W X Y Z

83 凱撒加密法 Julius Caesar (100BC~44AD)，羅馬皇帝，發明「凱撒加 密法」，亦稱「凱撒位移」 將每個字元往後推三個字元
明文：Meet me after the toga party 密文：PHHW PH DIWHU WKH WRJD SDUWB

84 凱撒加密法 將每一字母設定為數字(A=0, B=1…) 加密方法 解密方法 C=E(P)=(P + 3) mod 26
P=D(C)=(C – 3) mod 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

85 凱撒加密法應用 將 Caesar 加密演算法表示為 解密 暴力破解必須嘗試25種k值 C=Ek(P)=(P + k) mod 26
P=Dk(C)=(C – k) mod 26 暴力破解必須嘗試25種k值 k=1, 2, …, 25

86 凱撒加密法暴力破解 PHHW PH DIWHU WKH WRJD SDUWB oggv og chvgt vjg vgic rctva
nffu nf bgufs uif uphb qbsuz meet me after the toga party ldds ld zesdq sgd snfz ozqsx kccr kc ydrcp rfc rmey nyprw jbbq jb xcqbo qeb qldx mxoqv ： qiix qi ejxiv xli xske tevxc 密文 k=1 k=2 k=3 k=4 k=5 k=6 k=25

87 凱撒加密法 凱撒加密法課堂練習 密文為 “QXFTXK” 明文為？

88 Mono alphabetic 加密法 有別於Caesar加密法的全部位移k個位置 改為單一字母個別位移固定的位置
如 aS bA cH dV

89 破解Mono alphabetic 密文 明文=? 利用統計方式，分析字母出現頻率
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 明文=? 利用統計方式，分析字母出現頻率 P 13.33 H 5.83 F 3.33 B 1.67 C 0.00 Z 11.67 D 5.00 W 3.33 G 1.67 L 0.00 S 8.33 E 5.00 Q 2.50 Y 1.67 K 0.00 U 8.33 V 4.17 T 2.50 I 0.83 N 0.00 O 7.50 X 4.17 A 1.67 J 0.83 R 0.00 M 6.67

90 破解Mono alphabetic 一般英文文章中，字元相對出現頻率

91 破解Mono alphabetic UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a a VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th z a EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the t 逐一測試解密： it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

92 跳舞小人歷險記 摘自福爾摩斯(Sherlock Holmes) “the Adventure of the Dancing Men”
住在英國的Hilton Cubitt先生最近娶了美國Chicago的Elsie Patrick Cubitt在花園發現一張畫有跳舞的小人字條，Elsie一看， 臉色大變

93 跳舞小人歷險記 Cubitt寄給Holmes，並前往Holmes家說明所知的一切 Holmes直覺認為這是一個訊息，而非小孩子的塗鴉
因提供的字條太少，Holmes請Cubitt有看到新的，再傳給 Holmes看

94 跳舞小人歷險記 幾日後，Cubitt又在工具室門上發現粉筆畫的小人，並臨 摹下來寄給Holmes

95 跳舞小人歷險記 接下來的幾天，陸續在工具室發現小人圖，Cubitt全寄給 Holmes看

96 跳舞小人歷險記 Holmes將全部小人字條研究數天後，發現大事不妙，立即 趕往Cubitt家，欲阻擋悲劇發生
抵達Cubitt家後，Cubitt已受槍傷身亡，Elsie也身受重傷

97 跳舞小人歷險記 幾番調查後，Holmes終將案情查清楚，便寫下一紙條，派 馬童送至一間叫 “Elriges” 旅館的 Abe Slaney 先生 警察詢問Holmes為何對案情這麼了解，Holmes才開始說 明如何破解小人紙條

98 跳舞小人歷險記 Holmes分析所有的圖，發現 出現次數最多，便將此符號換成 “E” 因此圖4 能解讀成 “_E_E_”
可能為 “LEVER(槓桿)”, “NEVER(絕不)”, “SEVER(分開)”。Holmes猜測是NEVER。 因此大膽假設 便是 “Come Elsie”

99 跳舞小人歷險記 所以第一張字條 可以解開成 _M _ERE __E SL_NE_ AM _ERE A_E SL_NE_
AM HERE ABE SLANEY

100 跳舞小人歷險記 第二張字條亦可解讀 A_ ELRI_ES AT ELRIGES

101 跳舞小人歷險記 最後一張 ELSIE _RE_ARE TO MEET THY GO_
ELSIE PREPARE TO MEET THY GOD

102 跳舞小人歷險記 警察擔心兇手跳跑，Holmes說：「他等會兒就自己過來了」 Holmes稍早早已寫了字條請兇手過來
COME HERE AT ONCE

103 跳舞小人歷險記 Abe Slaney到場即被逮捕，才道出他是Elsie在Chicago的未 婚夫。Elsie發現Slaney和她父親組幫派為非作歹，才逃出 與Cubitt結婚

104 仿射密碼(Affine Cipher) 將字母轉換成數字(a=0, b=1, …, z=25) 加密： 解密：
C=E(M)=(aM+b) mod 26 a, b為整數，a必須與 26 互質 解密： M=D(C)=a-1(C-b) mod 26 a 1 3 5 7 9 11 15 17 19 21 23 25 a-1

105 仿射密碼(Affine Cipher) (3*7 + 8) mod 26 = 3  “D”
A與B事先協定好密鑰為 K=(3, 8) 加密函數 E(M) = (3M+8) mod 26 傳輸明文 “HIT”  (7, 8, 19) 加密： (3*7 + 8) mod 26 = 3  “D” (3*8 + 8) mod 26 = 6  “G” (3*19 + 8) mod 26 = 13  “N”

106 仿射密碼(Affine Cipher) “HIT”  “DGN” (3, 6, 13) 解密：
9(3 – 8) mod 26 = 7  “H” 9(6 – 8) mod 26 = 8  “I” 9(13 – 8) mod 26 = 19  “T”

107 仿射密碼(Affine Cipher) 課堂練習 C=E(M)=(aM+b) mod 26 K = (7, 4)
M = “HIT” (7, 8, 19) C = ? M=D(C)=a-1(C-b) mod 26 C1 = 49+4 mod 26 =1 C2 = mod 26 = 8 C3 = mod 26 = 7 M1 = 15(1 – 4) mod 26 = 7 M2 = 15(4) mod 26 = 8 M3 = 15(7 – 4) mod 26 = 19

108 Vigenère密碼 16世紀法國人Vigenère發展的多套字母替代法 (Polyalphabetic substitution)
使用區塊加密 加密 C=E(M)=M+k (mod 26) 解密 M=D(C)=C-k (mod 26)

109 Vigenère密碼 舉例 金鑰： “hsiuping” (7, 18, 8, 20, 15, 8, 13, 6) w e a r f m
l y 22 4 17 5 12 8 11 24 7 18 20 15 13 6 3 19 D W I L T N S P G 明文 金鑰 密文

110 Vigenère密碼 課堂練習 明文為 “ILOVETAIWAN” 金鑰為 “ROC” 密文 = ? ILOVETAIWAN
ROC Z Z Q M S V R W Y R B

111 Hill 加密法 由數學家Lester Hill於1929年發明 使用矩陣加密 金鑰 k= det k 必須與 26 互質

112 Hill 加密法 加密範例 明文為 “hsiuping” (7, 18, 8, 20, 15, 8, 13, 6) Ek(M)=
“hsiuping” 加密成 “ZPCAXZUL”

113 Hill 加密法 解密範例 先取得 k 之反矩陣

114 Hill 加密法 解密範例 每四個字母解密一次 “ZPCA” (25, 15, 2, 0) “XZUL” (23, 25, 19, 11)

115 Hill 加密法 課堂練習 k = m = “LOVE” C = ? “LOVE” = (11, 14, 21, 04) = [11 21]
[14 04] C1 = (1*11 + 1*14) mod 26 = (11+14) mod 26 = 25  “Z” C2 = (3*11 + 4*14) mod 26 = (33+56) mod 26 = 11  “L” C3 = (1*21 + 1*4) mod 26 = (21+4) mod 26 = 25  “Z” C4 = (3*21 + 4*4) mod 26 = (63+ 16) mod 26 = 1  “B” [C] = [25 25] [11 01] k^-1 = [04 -1] [-3 01] M1 = (4* *11) mod 26 = 11  “L” M2 = (-3*25 + 1*11) mod 26 = 14  “O” M3 = (4* *1) mod 26 = 21  “V” M4 = (-3*25 + 1*1) mod 26 = 4  “E”

116 Playfair加密法 1854年由英國科學家Sir Charles Wheatstone發明 使用 5 x 5 階字元矩陣
選定一金鑰，如 “hsiuping” 將金鑰從左上填入 I/J 視為同一字元 將剩餘字母一一填入 (不得重覆) H S I/J U P N G A B C D E F K L M O Q R T V W X Y Z

117 Playfair加密法 每次兩個字母加密一次 加密規則 H S I/J U P N G A B C D E F K L M O Q R T
如這兩個字母相同，則在其間插入一字元 如 balloon  ba lx lo on (插入x) 加密規則 同一列使用右邊的字母 同一行使用下面的字母 不同行、列 使用與同一行對應列 的字母 H S I/J U P N G A B C D E F K L M O Q R T V W X Y Z

118 Playfair加密法 金鑰： “HSIUPING” 加密 “computer” H S I/J U P N G A B C D E F K
“co”  “GT” “mp”  “TH” “ut”  “PR” “er”  “KO” H S I/J U P N G A B C D E F K L M O Q R T V W X Y Z

119 Playfair加密法 課堂練習 密鑰： “PLAYFAIR” 明文 “understood” 密文？
understood  un de rs to od un  PU de  IM rs  CO to  NQ od  TR

120 非對稱式加密系統 金鑰A 金鑰B 加密 以密文傳輸 解密 明文 加密演算法 解密演算法 (加密演算法的反向程序) 明文

121 RSA 出現在1977年，為最早的非對稱式加密系統，或稱公開金 鑰加密系統
由Ron Rivest, Adi Shamir 及 Len Adleman 發明

122 RSA金鑰產生 選定兩個質數 p, q 計算 n = p * q 計算 Φ(n) = (p – 1)(q – 1) 選取整數 e 計算 d
使得 gcd(Φ(n), e) = 1; 1 <e<Φ(n) 計算 d 使得 de mod Φ(n) = 1 公開金鑰： (e, n) 私密金鑰： (d, n)

123 RSA加解密 公開金鑰 (e, n) 私密金鑰 (d, n) 令明文 M < n 密文 C = Me (mod n)
明文 M = Cd (mod n)

124 RSA 舉例 選定 p=17, q=11 n=pq=17*11=187 Φ(n)=(p-1)(q-1)=16*10=160
選出 e 與 Φ(n) 互質，且 e<Φ(n)，e=7 計算 d，使得 de mod 160=1，d=23

125 RSA C = Me mod n= 887 mod 187 = 11 M = Cd mod n = 1123 mod 187 = 88
解密 M = Cd mod n = 1123 mod 187 = 88

126 隨堂測驗 p = 3, q = 11, e = 7, d = 3 明文 M = 5 求密文 C = ?
C = 5^7 mod 33=78125 mod 33 = 14 M = 14^3 mod 33 = 2744 mod 33 = 5

127 RSA安全分析 大質數 p, q 及 d 必須保密 若攻擊者取得 p, q 便得求出 d 對方加密給我們的密文，攻擊者皆可解開

128 RSA安全分析 RSA-1024bit 要破解RSA，必須取得p, q, d
代表 n 長度為1024-bit (309個十進位數字) 要破解RSA，必須取得p, q, d 雖然 n 為公開值，但從 n 因式分解求得 p, q 在目前是極為 困難的

129 RSA安全分析 n = 21, p = ?, q = ? (極為容易) n = 77, p = ?, q = ? (極為容易)
例如： n = 21, p = ?, q = ? (極為容易) n = 77, p = ?, q = ? (極為容易) n = 221, p = ?, q = ? (極為容易)

130 RSA安全分析 RSA 663-bit (200個十進位數字)
n = p = q = 因式分解極為困難

131 RSA安全分析 RSA 1024-bit (309個十進位數字)
n = p = ? q = ? 獎金 100,000 美金

132 破解RSA 155-bit 使用設備 破解時間 160部 175-400 MHz SGI and Sun workstations
8部 250 MHz SGI Origin 2000 processors 120部 MHz Pentium II PCs 4部 500 MHz Digital/Compaq boxes 破解時間 1999年3月17開始 1999年8月22因式分解成功

133 RSA因式分解挑戰 http://www.rsasecurity.com/rsalabs/node.asp?id=2092
Challenge Number Prize ($US) Status Submission Date Submitter(s) RSA-576 $10,000 Factored December 3, 2003 J. Franke et al. RSA-640 $20,000 November 2, 2005 F. Bahr et al. RSA-704 $30,000 Not Factored RSA-768 $50,000 RSA-896 $75,000 RSA-1024 $100,000 RSA-1536 $150,000 RSA-2048 $200,000

134 駭客練習 請登入以下網站： 共五關