Science Focus ( Issue 21)

19 To encrypt the letter “H”, Cliff now has to find my public key. He reads from the directory that n = 143 and e = 7. The encrypted text is given by c = T ^ e (mod n ). Here our text T 1 = 72, so the encrypted text is c 1 = 72 ^ 7 (mod 143), a very intimidating expression that seems impossible to compute by hand. But we can enlist the help of computers – and a quick Google reveals that c 1 = 19 (mod 143). So the first number we need to send is 19. We repeat the above procedure for the letter “i”: c 2 = 105 ^ 7 (mod 143), so the second number is c 2 = 118 (mod 143). So the message “Hi” becomes “19 118”. To the outsider, it is impossible to recover the original message, since you cannot reverse your way from a modular number; however, you have one extra edge – the values of p and q – that sets you apart. Without them, you would need to factorize n , which is extremely time consuming since n is very large. The key to decryption is calculated from the following formula: take the least common multiple of p - 1 and q - 1, lcm (10, 12) = 60. The decryption key d is given by the following equation: 1 = ( e x d ) mod (lcm ( p - 1, q - 1)). In our case, 1 = (7 x d ) mod 60; so d = 43. This is our magical number to get back the message. And finally the decrypted message, m , is given by m = c ^ d (mod n ). We have received two letters, so we will decrypt them separately: The first letter is 19 ^ 43 (mod 143), which gives us 72 (mod 143), the letter “H”; similarly, the letter “i” comes from 118 ^ 43 (mod 143) = 105 (mod 143). These look like calculations involving awfully large numbers, but computers can do them extremely easily. Also, with d , you can now decrypt every single message that Cliff sends you afterwards (footnote 5). The encryption works because of a theorem known as Fermat’s Little Theorem – although by the same person, it is not the infamous Fermat’s Last Theorem. The theorem looks rather innocent at first sight: a ^ p ≡ a (mod p ) for any prime p (footnote 6) – but is in fact key (pardon the pun) to why the encryption works, since the exponential features multiple times. The proof requires a bit of machinery that can be easily found on Wikipedia, and we will skip that for now. Cur rently the RSA cryptosystem is seen as the default choice for encrypting small amounts of data, such as keys to symmetric key cryptography (footnote 7). The largest known factorized n is 250 digits long (829 bits), which took 2700 core years (footnote 8), and was factorized in 2019 [2]. The usual length used for encryption, in contrast, is 2048 bits, so we are still safe for the time being. However, history tells us that the codebreakers will always catch up – and we will need to find a new encryption method in the future. 1 Actually, the first inventor of the RSA was Clifford Cocks, an English mathematician, who described the algorithm four years ahead (1973) of Rivest, Shamir and Adleman (1977); sadly, he worked for the British Intelligence Agency, and his work wasn’t released until more than 20 years later in 1997, so RSA got all the credit. 2 That, however, may change with quantum computing, but at the moment quantum computers are not fast enough to hack RSA yet. If you’re interested, try Googling “Shor’s Algorithm”. 3 There is a slight catch, however; in 12-hour time system, when telling the time we say 12 o’clock when the clock strikes twelve, but in modular arithmetic we say 12 ≡ 0 (mod 12) instead. 4 Bit is short for “binary (base 2) digit”– so a 7 bit number ranges from 1 to 2 7 - 1 = 127, and 2048 bits range from 1 to 2 2048 - 1, around 617 digits. 5 The equation always has a unique solution d because we assumed that e is coprime with 10 and 12 from the beginning. 6 This equation is in modular arithmatic, not the algebra that most of us are familiar with. It actually means a ^ p (mod p ) ≡ a (mod p ). 7 RSA is the key (pun intended) component of the larger cryptographic protocol called TLS (Transport Layer Security), used for many online transactions and communication. 8 The term “core year” refers to the equivalent of using one CPU core continuously for a year (365 days). The author uses Intel Xeon Gold 6130 CPUs as a reference [2]. WhatsApp 的新使用者授權合約成為了前陣子的全城 熱話，也再次引起了大家對網絡安全的討論。我們經常看 到「此對話已進行端對端加密」之類的訊息 — 可是，你有 想過現代的加密過程到底是怎樣運作的嗎？我們又有多安 全？ 如果你有玩過密室逃脫遊戲的話，你應該碰到過一兩組 密碼（cipher）— 就是那些看似無意義的亂碼，然而你必先 解開箇中玄機才能逃脫。最著名的加密法大概是羅馬帝國 時代的凱撒加密法（Caesar cipher），它把所有字母都按 字母排列順序偏移某個數值的位置。可是，凱撒密碼也是最 容易解開的密碼，因為我們可以對其進行頻率分析。在英文 裡有著幾個最常出現的字母，譬如在這篇文章的英文原文 裡，英文字母「e」到此為止已出現了 81 次，比其他字母都 要多。解密者可以看看凱撒密碼裡哪個字母出現次數最多， 那就不難猜到原文被順移了多少個字母。 從此，不同的加密法陸續誕生。與其只將每個英文字母 按一定數值的位置偏移，人們開始將字母根據一個字，甚至 一段文字進行不同的偏移，稱為維吉尼亞密碼（Vigenère cipher）。不斷複雜化的加密法，最終造就了著名的恩尼格 瑪密碼機（Enigma），它的基本上是一系列相當聰明的字 母偏移。儘管複雜如此，也眾所周知地被 Alan Turing 在英 國政府的解密基地—布萊切利園（Bletchley Park）破解了。 這件事發生之後，大家都意識到發展嶄新加密法的需要。 然後是 RSA。它是現代加密的主要方法，以三位發明家 Rivest、Shamir 和 Adleman 的姓氏命名（註一）。RSA 加 密演算法和以上提到的加密法有著本質上的不同，凱撒加 密法和恩尼格瑪密碼機使用對稱金鑰（symmetric keys），