今日推薦開源項目：《99 jikeaiqing》
今日推薦英文原文：《How Prime Numbers Keep the Internet Secure》
今日推薦開源項目：《99 jikeaiqing》傳送門：項目鏈接
推薦理由：難得的 99 之日，如果自己沒有可以 99 的人，看一些別人的故事也未嘗不可。這個項目就是一個非常適合 99 之日看的日常故事集，輕鬆的日常故事再加上情侶元素自然對於這一日再合適不過。
今日推薦英文原文：《How Prime Numbers Keep the Internet Secure》作者：Sun-Li Beatteay
原文鏈接：https://medium.com/better-programming/how-prime-numbers-keep-the-internet-secure-680cc1743133
推薦理由：別看質數好像沒什麼存在感，在安全方面可是很重要的
How Prime Numbers Keep the Internet Secure
And why life wouldn』t be the same without them
Whether you know it or not, you use prime numbers every day. Do you see that lock symbol in the address bar of your web browser? The one that looks like this:
Image credit: author
That lock means you』re using prime numbers at this very moment. That』s because the internet uses prime numbers. In fact, prime numbers are so ingrained into the fabric of our daily lives that the world would be a drastically different place without them. We』d still be doing all our banking in person and buying everything in cash. And forget about texting, because we』d still all be pen pals.
So what is it about prime numbers that makes them so special? To answer that, let me ask you a simple question: Is this a prime number?
9307398526401816703683197763617206082269079617576835286211259044095385462270542532346398139788788003092515521098292832872130802035097419307557532476688657
If you said, 「I have no idea,」 you wouldn』t be alone. No one would know at first glance. The natural instinct might be to search for an online program that could check if it was prime. The problem is that that number is too large for online prime-number checkers. They』ll all say it』s not a prime number — whether it is or not — because they can』t store it in memory.
The next inclination might be to write your own function or use one from a programming library. Go ahead, try it. Here, I even wrote a simple function you can try yourself:
function isPrime(n) {
n = BigInt(n);
if (n <= BigInt(3)) {
return n > BigInt(1);
} else if (n % BigInt(2) === 0 || n % BigInt(3) === 0) {
return false;
}
let i = BigInt(5);
while ((i*i) <= n) {
if (n % i === 0 || n % (i + BigInt(2)) === 0) {
return false;
}
i += BigInt(6);
}
return true
}
isPrime(9307398526401816703683197763617206082269079617576835286211259044095385462270542532346398139788788003092515521098292832872130802035097419307557532476688657);
There』s one major problem — it won』t finish. At least not for a long, long, long time. The reason is that it』s computationally expensive to detect if a number is prime. There are certain methods, such as the Miller-Rabin primality test, that are very fast. But for large enough numbers, it』s still slow.
And the fact that it』s inefficient to detect if a number is prime makes it a useful tool for encryption!
Encryption
For those who don』t know, encryption is the act of turning information into an unreadable format called a cipher. Decryption is the opposite process of turning a cipher back into the original information.In other words, encryption allows us to keep information private and out of the hands of people who might use it for malicious purposes. That』s why it has become a cornerstone of the modern internet.
Without encryption, I wouldn』t be able to do most of the things I do online, such as buy groceries, pay off debts, or message my friends — at least not securely. Encryption prevents hackers from stealing my banking information and spying on my private conversations.
It』s not just the internet that uses encryption but many modern devices, such as computers, smartphones, or even smart fridges. They all use encryption. Suffice it to say, encryption is important and everywhere.
But how does encryption work?
Encryption algorithms use keys to encrypt and decrypt data. How those keys are used depends on the type of encryption, of which there are two: symmetric and asymmetric. Both of which have different use cases.
Symmetric encryption
Symmetric encryption. Image credit: Ons Jallouli via ResearchGate.
Symmetric encryption gets its name because it uses the same key for both encryption and decryption. Since it uses a single key for both encryption and decryption, symmetric encryption is very fast — but fragile. The key must always be kept private and only shared between trusted parties.
Because of this, one of the main uses for symmetric encryption is securing data at rest. This means encrypting devices like computers, databases, or IoT devices. If you remember the drama that occurred between Apple and the FBI — that was a battle over iPhone encryption.
While symmetric encryption works well, it has an inherent flaw. In order for multiple parties to have encoded communication via symmetric encryption, they must all agree on a key ahead of time. And in the context of the internet, where you』re communicating with hundreds of servers a day half-way across the world, that』s not possible.
That』s where asymmetric encryption comes in.
Asymmetric encryption
Asymmetric encryption. Image credit: Ons Jallouli via ResearchGate.
Asymmetric encryption uses two keys, one for encryption and one for decryption. This works because the keys are complements of one another. When they』re used together, they cancel each other out — similar to how complement colors cancel one another out into white.
Image credit: author
The key used for encryption is known as the public key. As you might guess, it』s safe to share this key with anyone.
The decryption key, on the other hand, is called the private key because it must be kept private. Only the holder of the private key can decrypt ciphers that were encrypted with the public key. Even if a malicious user were to intercept a ciphertext, they』d just see gibberish.
This makes asymmetric encryption an ideal tool for sharing sensitive data. Not only that, but since a private key should only be owned by a single entity, it works well for authentication as well. That』s exactly how it』s used in the TLS handshake.
The trapdoor
One of the reasons that asymmetric encryption is as important as it is is because it works as a trapdoor function.
Image credit: author
This means it』s very simple to execute in one direction but very difficult to reverse — unless you have special information, otherwise known as the trapdoor or secret.
In the context of asymmetric encryption, it』s very simple to encrypt data but very difficult to decrypt it using only the public key. It becomes simple again with the private key.
But not all asymmetric-encryption algorithms are built the same. How laborious it is to reverse the trapdoor function determines an algorithm』s security. To see just how secure asymmetric encryption can be, let's explore one of the most popular algorithms in use today: RSA.
RSA encryption
RSA was invented in 1977 by three cryptographers: Ron Rivest, Adi Shamir, and Leonard Adleman — hence the name. Since its inception, it has spread to nearly every corner of the earth.If you』ve ever used Secure Shell (SSH) …
An example SSH private key. Image credit: author.
… or GNU Privacy Guard (GPG) …
Example GPG key. Image credit: author.
… you have RSA to thank for it. However, it』s most known for its use in TLS and HTTPS to prevent man-in-the-middle attacks.
RSA in a TLS handshake. Image credit: author.
While RSA is nearly half a century old, it』s one of the most commonly used asymmetric-encryption algorithms in the world. Its ubiquity is a testament to its security.
But why is it so secure? Short answer: prime numbers. Long answer? That』ll involve some math. But the best answer would be to try and break it ourselves.
Breaking RSA
Here』s the scenario: We』re hackers trying to impersonate Medium』s server. We want to intercept all traffic going to Medium』s website in order to steal user credentials and ransom their data.Using Wireshark, we』re able to get a copy of Medium』s RSA public key and website certificate.
Medium』s RSA public key as seen in Wireshark. Image credit: author.
But in order to impersonate Medium and fool users into connecting to our phishing server, we need the private key. Luckily, all is not lost.
One thing I haven』t mentioned is that RSA keys are just numbers. An RSA private key is just a single number, which we』ll call d. The public key is made up of two numbers, e and N. And N is the product of two more numbers, p and q.
I know, that』s a lot of numbers to track of. But it』s just those last two numbers, p and q, that we need to focus on. Because according to RSA』s key-generation algorithm, if we know e, p, and q, we can recreate the private key.
「Well, perfect,」 one might say. 「Since we have the public key, we know e and N. And since we know N, we just need to split it apart to get p and q. How hard could that be?」
Not so fast, person I just made up to ask loaded questions — p and q are prime numbers. Gasp!
I mentioned before that detecting if a number is prime is hard. What』s even harder is prime factorization.
How hard, you might ask?
Very hard. Image credit: author.
RSA typically uses numbers 1024, 2048, or 3096 bits long. As you can see in the graph above, it only takes seconds to minutes to create N, but it』d take millions to billions of years to factor it apart.
The reason for this is — for average, nonquantum computers — the best approach to factoring numbers is brute force. And to brute force through a number like this is going to take a while:
12647218591793774062037539860814590913847656969568852342569985866826731647633698490555162899129013020883082990527279827064849704038819915244363097120031062841681483530795022535252488366169730386558454292994968234214045666016756933262308367238453012386845278265898125397947728757013541963782671274800429212175737617916738370351721854897974375037404102868790995317383226110430324268401945063200233204784127599950729869495397377610047121343931821194220803396259107891220452870079636709770538139479748696178546655932056530040495898965404702415803790560056325250086900175615221136804225865647753477561884491932551643726743
While it』s not impossible, the level of effort is astronomical and not worth it. We』d all be long dead by the time we could generate Medium』s private key.
So long story short, prime numbers are pretty darn hard to break. And that』s how they keep the internet secure.
Parting Thoughts
As a software developer, I』m often intimidated by all the different moving parts on the internet. It can feel like a magical and bewildering place. And as a result, I usually feel like I have no idea how any of it works or what I』m doing.But any time I learn something new about the systems I use on a daily basis, the world becomes just a little less chaotic and magical. I hope this article has helped demystify some of the mysteries of the internet for you as well.
And in case you were wondering, the prime number from the very beginning of this article isn』t prime.
下載開源日報APP：https://openingsource.org/2579/
加入我們：https://openingsource.org/about/join/
關注我們：https://openingsource.org/about/love/
