好人勿用™

關於部落格
心寬念純●一生懸命●大願成就●幸福長久
  • 123832

    累積人氣

  • 14

    今日人氣

    0

    訂閱人氣

RSA (Cryptosystem)

言歸正傳... 神乎技矣RSA~~~

 RSA Key Pair Gen:

1. 選取任意兩質數,且p!=q => p=13 q=53
2. 計算n=p*q => 13×53=689
3. By Euler's totient function,
    計算m=ø(n)=(p–1)(q-1) = 12×52=624 不大於n且與n互質的整數個數為(p-1)(q-1)
4. 選取任意一整數e與m=ø(n)互質,且1<e<ø(n),使得d=gcd(e,ø(n))=1成立! (em)
    By Modular multiplicative inverse, d=e^-1 mod (ø(n))
    e=7 by Modular multiplicative inverse, d=535 (<= 這玩意不好算...)


5. 發佈公鑰KU={e,n} = {7, 689}
6. 保存私鑰KR={d,n} = {535, 689}


7. 最後公開公鑰e與n,保密專鑰d,銷毀p與q
8. C = M^e mod (n)    // M為明文, C為密文
9. M = C^d mod (n)    // M為明文, C為密文


RSA的可靠性是建立在對極大整數做因數分解的難度上...
換言之, 對一個極大整數"n"做因數分解愈困難, 表示RSA就愈可靠!!!

         n=p*q

p和q還要滿足一定的要求,首先它們不能太靠近!
此外(p-1)或(q-1)的因子不能太小, 否則的話n也可以被很快地分解...


@ 1990年有人證明:
假如p大於q而小於2q(這是一個很常的情況)
而d<1/3*n1/4,那麼從n和e可以很有效地推算出d

   此外e=2, KU{2,n}應該永遠不能被使用!!!

RSA How It Work?


M=78, Encyption by KU{7,689}
C=221, Decryption by KR{535,689}


 可以使用小算盤驗算一下...
左圖: Encryption                  右圖: Decryption


 其實... 也可以用Private Key來加密~
RSA也可以用來為一個訊息署名(SIGN): Hach with Encryption by Private Key.

把要傳送的M計算一個Hashes,然後用私鑰(Private Key)把Hashes加密,
並將這個SIGN(署名)加到M訊息中一併傳送出去~~~


M=78, Encyption by KR{535,689}
C=117, Decryption by KU{7,689}


 非常可怕的應用... 電腦病毒 (幾乎不可逆!)

Bounded gaps between primes (質數之間的有界距離) by 張益唐

他的「髮絲步」撞破數學界的「質數牆」 華人數學家張益唐破解百年數學謎題
結論: 不管任何的, 多大的相鄰質數, 一定找的到差距小於7,000萬的相鄰質數!
        (給定任何正整數M,一定找得到相鄰質數P與Q皆大於M,使得P跟Q的差距小於七千萬)

根據PolyMath最新公布的結果: 
目前相鄰質數的差值(Bounded gaps between primes), 已逼近到4,680

ABC猜想 @ 數學界最大的謎團:日本數學家望月新一的論文與無法測透的證明
結論: 沒人看得懂望月新一在寫什麼! 但工藤新一說... 真相只有一個!!! 就是我們太弱了...

RSA numbers @ https://en.wikipedia.org/wiki/RSA_numbers#RSA-2048

RSA-2048 @ 617 decimal digits (2,048 bits)
      2519590847565789349402718324004839857142928212620403202777713783604366202070
      7595556264018525880784406918290641249515082189298559149176184502808489120072
      8449926873928072877767359714183472702618963750149718246911650776133798590957
      0009733045974880842840179742910064245869181719511874612151517265463228221686
      9987549182422433637259085141865462043576798423387184774447920739934236584823
      8242811981638150106748104516603773060562016196762561338441436038339044149526
      3443219011465754445417842402092461651572335077870774981712577246796292638635
      6373289912154831438167899885040445364023527381951378636564391212010397122822
      120720357


(8-) 這一大串可比擬為宇宙中的中子數量! 光要寫下來就不簡單! 更何況還要做因數分解!!!)

2016大選後同場加映...  #689

What's Special About This Number?


       689.11 vs 689.47
 

689 is an amazing number for several reasons.

# 689 is the sum of consecutive prime numbers 227, 229, and 233.

# 689 is the sum of the primes from 83 to 109.
    Do you know what those 7 prime numbers are? Ans:
83, 89, 97, 101, 103, 107, 109

#689 = 9種3個不同數字的平方加總!!!


反正()都一個樣... 689屎出包個拉馬蹄克!!!


 689 is the same number when it is turned upside down.
Numbers with that characteristic are called Strobogrammatic numbers.
(屎出包個拉馬蹄克 = 這玩意竟是如何翻譯! 哈~)

      A2 + B2 =  689 (斜邊) By 畢氏定理


#689 = 三種連續的數的加總:
            (is the sum of consecutive numbers three different ways)

689 = 344 + 345;                                     // that’s 2 consecutive numbers.
689 = 47 + 48 + 49 + 50 + 51 + 52 + 53 + 54 + 55 + 56 + 57 + 58 + 59;
                                                               // that’s 13 consecutive numbers.
689 = 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27
+ 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 39 = 689;          
                                                               // that’s 26 consecutive numbers.
==========================================================
1.) 689 is a composite number. (689為合數)
2.) Prime factorization: 689 = 13 x 53. (只能被因式分解成13*53)
3.) The exponents in the prime factorization are 1 and 1.
      Adding one to each and multiplying we get (1 + 1)(1 + 1) = 2 x 2 = 4.
      Therefore 689 has exactly 4 factors.
4.) Factors of 689: 1, 13, 53, 689 (只有四個因數)
5.) Factor pairs: 689 = (1 x 689) or (13 x 53)
6.) 689 has no square factors that allow its square root to be simplified.
     √689 ≈ 26.248809. (沒有平方根)
==========================================================

 RSA網誌的最後...
Combo™必須借用... 王羲之快雪時晴帖解碼作為Ending!!!
 
   康寶頓首。陰符佳。
                 想善。未果為結。力不次。黃康寶頓首。麻省三侯。

[眉批] 一直覺得RSA就是快雪時晴帖~ 神乎技矣的妙!!!
         而其命運亦然, 嚴格來說... RSA應該只是... Clifford Cocks的摹本~ 打完收工...
 

 
      快雪時晴RSA 力不次
 
          黃康寶™頓首
 
      Made In Taiwan @ 689


 同場再加映... "快" & "晴"系列~
富嶽三十六景:凱風快晴 (赤富士) By 葛飾北齋





 




RSA 非對稱型加解密演算法 - 使用 C 語言實作
http://www.codedata.com.tw/social-coding/rsa-c-implementation/

爾虞我詐 by Cryptography
http://blog.yam.com/combo/article/123066678


相簿設定
標籤設定
相簿狀態