RSA (Cryptosystem)－好人勿用™

RSA (cryptosystem)
是1977年由Ron Rivest,Adi Shamir和Leonard Adlemann所共同提出 @ MIT

(@1973年英國政府通訊總部工作的數學家Clifford Cocks
於一個內部文件中提出了一個相同的算法,但他的發現被列入機密!一直到1997年才被發表!)

RSA Patent @ US4405829 A (專利已失效!)

質數 (Prime number):
指在大於1的自然數中, 除了1和該數自己本身外, 就無法再被其他自然數整除的數!
圖像裡可能有夜晚

Prime number by κόσκινον Ἐρατοσθένους

所有小於1000的質數為:(Total 168)
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, (83, 89, 97,
101, 103, 107, 109), 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, (227, 229, 233), 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Free Mersenne Prime Search Software

Prime95 @ http://www.mersenne.org/download/
Marin Mersenne

Mersenne prime:
梅森質數指的是任何可以寫成2^P-1的質數,而質數已被證明是無窮盡個!!!

不過可惜的是，梅森終究還是搞錯了。
2⁶⁷ －1 和 2²⁵⁷ －1 後來都被發現並不是質數，只不過前後花了長達 300 年的時光。

目前已知最大的梅森質數: Largest Known Prime Number: 282,589,933-1

(有多大呢? 使用txt紀錄再用zip壓縮還要11.1Mega!!!)

M_82589933= 2^82589933-1
// since 2018.12.21
最小的梅森質數: 3 (=2²-1) // since 公元前5世紀

Intel Skylake Bug for Prime
~~更大的質數找到啦！花了4年時間、有1千7百多萬位數 @ 2013-01-25~~

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

~Let's Practice 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成立! (e ⊥ m)
   By Modular multiplicative inverse, d=e^-1 mod (ø(n))
    e=7 by Modular multiplicative inverse, d=535 (<= 這玩意不好算...)

(https://planetcalc.com/3311/)

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*n^1/4,那麼從n和e可以很有效地推算出d

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

RSA How It Work?
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訊息中一併傳送出去~~~
SIGN RSA_SIGN
How It Work-3
M=78, Encyption by KR{535,689}
C=117, Decryption by KU{7,689}

非常可怕的應用... 電腦病毒 (幾乎不可逆!)
CryptoLocker:勒索軟體解析：技術上真的無法自行救回檔案

CryptoLocker

CrypBoss、HydraCrypt、UmbreCrypt等勒索軟體已成功破解
undefined

P@ssw0rd

專家告訴你，就算把密碼設置為「jK8v!ge4D」仍然不安全
https://www.techbang.com/posts/78988-experts-tell-you-that-even-setting-the-password-to-jk8vge4d-is-still-not-secure

2015 年最弱密碼，123456 穩坐冠軍
http://technews.tw/2016/01/20/2015-dress-code-123456/

2013 年最糟糕的密碼是 123456
http://technews.tw/2014/01/21/123456-is-worst-password-of-2013/

PW123456

質數同場加映...
Bounded gaps between primes (質數之間的有界距離) by 張益唐

[No Caption]
他的「髮絲步」撞破數學界的「質數牆」華人數學家張益唐破解百年數學謎題
結論: 不管任何的, 多大的相鄰質數, 一定找的到差距小於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

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

2016大選後同場加映... #689
一張圖讓你秒懂台灣政局 (https://news.ltn.com.tw/news/politics/breakingnews/1577855)

What's Special About This Number?

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

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=9種3個不同數字的平方加總
689 is the same number when it is turned upside down.
Numbers with that characteristic are called Strobogrammatic numbers.
689從每個方向看都長一樣
(屎出包個拉馬蹄克 = 這玩意竟是如何翻譯! 哈~)

      A² + B² = 689 (斜邊) By 畢氏定理
689-pythagorean-triples
#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. (沒有平方根)
==========================================================