看板 Gossiping作者 jayfrog (寫不出coding)標題 Re: [問卦] 質數到底有什麼用?時間 Sun Mar 8 23:58:36 2015
在密碼學裡面,不止於RSA,諸多密碼系統也都有對於「質數」的需求
例如說RSA的金鑰由兩個質數PQ構成,
如果今天不小心,P不是質數,RSA演算基本還是能用,
但是暴力搜尋法的複雜度(安全性)至少砍半,少很多,更不用說其他攻擊法
或是橢圓曲線加密的橢圓曲線群的大小,也會要求是質數,
--
恩~~在很多密碼系統中,所需要的是 group(群),這個代數架構。
而剛好((Z/pZ)*,*) 剛好是一個group,所以就拿來在密碼系統用。
而group有什麼好處呢?因為group具有封閉性,你任拿其中兩個元素運算,他還會是
在這個group裡。所以我們不用怕會有什麼奇怪的東西跑出來。
然後要讓這個密碼系統難破的的話,我知道是使用所謂的離散對數的難題。
什麼是離散對數呢? 任給兩個數a,b 求m a^m=b+Qp,用中文來說就是 a的多少次方除以
p餘數才會是b。 而在這通常p是質數,因為質數不可分的性質才會對任意的a都會有解
(ps.其實在這裡的group是要有特定條件的群,只是我忘了是什麼…不好意思,學藝不精)
也因為在密碼系統中,他們所需要的東西是代數架構這種東西,所以只要符合他們條件的
代數架構都可以拿來用。
在小談一下,費馬小定理的證明,那就是因為((Z/pZ)*,*) 是一個group Q.E.D.
這就是group的力量(被歐)
再來補充一下,橢圓曲線群 over Fp 的個數不一定會是質數是就了。
http://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves
Counting points on elliptic curves - Wikipedia, the free encyclopedia E.g. the last row is computed as follows: If you insert in the equation you get as result (2nd column). This result can be achieved if . So the points for the last row are because is fixed as it is the result and if is positive and if is negative. Remember that equals over . ...
wiki裡有簡單的例子可以看一下。
大概就是這樣,如果有錯請多多指教。
--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明,
但 4 年實在太短,沒有足夠的時間容我來證明它。」
轉自 <廢馬大定理>-民明書坊
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.199.231
※ 文章代碼(AID): #1K_76vVr (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425830329.A.7F5.html
※ 同主題文章:
Re: [問卦] 質數到底有什麼用?
03-08 23:58 jayfrog.
推 mp60707: 我懂了 樓下不懂別裝1F 03/08 23:59
推 ppder: 趕快推 不然別人以為我......2F 03/09 00:00
推 abb1213: 快推不然別人說我不懂4F 03/09 00:00
推 diding: 簡單來說就是質數很重要恩恩 我懂了7F 03/09 00:01
→ ma4wanderer: ...你離散對數問題好像搞錯了 費馬小定理也搞錯了12F 03/09 00:05
感謝指正 離散對數的問題
→ h2o1125: 費馬小定理沒錯 可以推過去13F 03/09 00:06
有largrange 是euler theorem嗎?
a^(phi(m))= (1 mod m)
→ h2o1125: 不用喔 triially Zp* is a finite group i.e. Z^(p-1)=117F 03/09 00:09
推 CKLee: 幫樓主修正一下,其實(Z/pZ,*)不是群,因為0沒有反元素...妳要把零扣掉,變成((Z/pZ)^x,*)才是群 :)18F 03/09 00:11
感謝指正,自己在看的時候會知道,不過常常寫出來的時候就會忘記加
推 joesarira: 恩.................................... (爆炸20F 03/09 00:12
推 CKLee: 幫補充什麼是Lagrange's Theorem: H是G的subgroup且|G|有限則 |H|整除|G|21F 03/09 00:14
我知道這個定理(不過忘了名字,教授別罵我),
但我不清楚這個定理跟費馬小定理之間的關係就是了
→ ma4wanderer: 所以一個元素的order=其循環群的大小 整除原本的25F 03/09 00:16
推 CKLee: 和費馬小定裡的關係是這樣:給一個非零的a。那根據Lagrange定理,<a>||G| = p-1,所以很快得到a^(p-1) = 1 => a^p = a(mod p) 如果 a = 0 是 trivial,證畢。28F 03/09 00:19
感謝指導。
推 CKLee: 忘了講,上面的 a 非零是在 Z/pZ 中非零31F 03/09 00:23
→ ma4wanderer: 啊 對了 補充一下 橢圓曲線群的大小不見得是質數沒錯但會要求是質數
不然會被normal group作解析32F 03/09 00:24
不知道要看什麼書還是paper,才能知道elliptic curve group over finite field
的個數需要被要求是質數?
推 Aesti: 好,我老實承認我看不懂35F 03/09 00:27
推 ma4wanderer: 漏打 拍謝 我是要說"橢圓曲線加密"的橢圓曲線群
大小要求是質數36F 03/09 00:36
恩~~那有相關的資訊嗎?還是有什麼kye word 可以拿來google。謝謝
感謝大大的提供。八掛版果然人才濟濟。
※ 編輯: jayfrog (118.160.199.231), 03/09/2015 00:51:42
推 j83ne04: 早八第一堂網路安全 滑個PPT還看到這篇40F 03/09 08:44
--