→ springgod:原來如此~~^^ 推140.112.251.218 12/28
→ Ethicizer:喔喔喔 推 140.117.182.65 12/28
→ Ethicizer:因式分解大數無捷徑呀... 推 140.117.182.65 12/28
※ 引述《hanshiuan (黃皮)》之銘言：
: ※ 引述《same (慢慢)》之銘言：
: : 有實作啦，不過到現在都還只做出幾個 bit 而已，因為干擾很嚴重，
: : 很不好實作，所以真要實用，除非再來一個曼哈坦計劃等級的趕工，
: : 不然十年內應該還看不到一台可用的產品。
: 請問一下，什麼是①質數加密法～
: ②量子電腦～ 啊？？ 謝謝
(1) 質數加密法
今天選兩個質數 P,Q (ex: P=3,P=5 )
另 N = P x Q ( N=15 )
再取一個與 P-1 Q-1 互質的 E ( E = 3 )
P和Q是自己知道的, 別人都無法知道
N,E是任何人都可以知道的
今天別人有一個數字M要傳給我 (M=12)
我要他加密後再傳給我
他要做 C = M^E mod N (M^E=1728, (1728 mod N) = 3)
然後再把 C 丟給我 (C = 3, 由上式)
C就是經過加密的資料
我收到C後,只要先找到一個D, 符合下式
E * D mod (P-1)x(Q-1) = 1 (D = 3)
然後再做
M = C^D (mod N) (C^D=27 ,(27 mod N) = 12)
就得回 M 了 (M = 12)
很神奇吧..中間的C被人得走的話..他也無法解碼..
因為解碼最重要的一步就是要找出一個 D
D符合 E * D mod (P-1)x(Q-1) = 1
但是別人不知道 P,Q 分別是多少
只知道 N = P x Q
你可能會認為 N = P x Q 因式分解馬上就能找出來兩個質數..
但是當P,Q選的是數百位數, 數千位數的兩個質數呢??
隨便找個質數很快..好像有聽說一百位數的話平均六百個數字就有一個質數
用亂數亂選很快就能找出一個很大的質數
但是要從一個很大的數字 N 中找出他是哪兩個質數相乘就要很久的時間..
所以 質數加密法 是很難破解的
需要很長很長很長的時間
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.95.27