自然数 素数 质数_素数如何确保互联网安全

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:

不管您是否知道，每天都使用质数。 您是否在网络浏览器的地址栏中看到该锁定符号？ 看起来像这样的一个：

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
}

You can copy and paste that into your browser console or node REPL and call:

您可以将其复制并粘贴到浏览器控制台或节点REPL中，然后调用：

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.

有一个主要问题-它不会完成。 至少没有很长一段时间。 原因是检测数字是否为质数在计算上是昂贵的。 有某些方法非常快，例如Miller-Rabin素数检验 。 但是对于足够大的数字，它仍然很慢。

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.

对于那些不知道的人， 加密是将信息转换为称为cipher的不可读格式的行为。 解密是将密码转换回原始信息的相反过程。

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 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.

因此，对称加密的主要用途之一是保护静态数据 。 这意味着加密设备，例如计算机，数据库或IoT设备。 如果您还记得苹果公司和联邦调查局之间发生的戏剧性事件，那是一场关于iPhone加密的斗争。

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.

尽管对称加密效果很好，但它具有固有的缺陷。 为了使多方通过对称加密对通信进行编码，他们必须都提前同意密钥。 在Internet的背景下，您一天中途要与数百台服务器进行通信，这是不可能的。

That’s where asymmetric encryption comes in.

那就是不对称加密的来源。

非对称加密 (Asymmetric encryption)

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.

非对称加密使用两个密钥，一个用于加密，一个用于解密。 之所以可行，是因为密钥是彼此的补充。 当它们一起使用时，它们会互相抵消，就像补色互相抵消成白色一样。

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.

这使非对称加密成为共享敏感数据的理想工具。 不仅如此，而且由于私钥只能由一个实体拥有，因此它也很好地用于身份验证。 这就是TLS握手中使用的方式 。

活板门 (The trapdoor)

One of the reasons that asymmetric encryption is as important as it is is because it works as a trapdoor function.

非对称加密之所以如此重要的原因之一是因为它可以用作活板门功能 。

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 。

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.

RSA于1977年由三位密码学家发明：Ron Rivest，Adi Shamir和Leonard Adleman，因此得名。 自成立以来，它已蔓延到地球的几乎每个角落。

If you’ve ever used Secure Shell (SSH) …

如果您曾经使用过Secure Shell(SSH )…

… or GNU Privacy Guard (GPG) …

…或GNU Privacy Guard(GPG) …

… 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。 但是，它因在TLS和HTTPS中用于防止中间人攻击而闻名。

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.

虽然RSA已有近半个世纪的历史，但它是世界上最常用的非对称加密算法之一。 它的普遍存在证明了它的安全性。

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.

但是为什么这么安全？ 简短的答案：质数。 长答案？ 那将涉及一些数学。 但是最好的答案是尝试自己打破它。

破解RSA (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.

场景如下：我们是黑客，试图模仿Medium的服务器。 我们想拦截所有进入Medium网站的流量，以窃取用户凭据并勒索其数据。

Using Wireshark, we’re able to get a copy of Medium’s RSA public key and website certificate.

使用Wireshark，我们可以获取Medium的RSA公钥和网站证书的副本。

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.

我没有提到的一件事是RSA密钥只是数字。 RSA私钥只是一个数字，我们将其称为d 。 公钥由两个数字e和N组成 。 N是另外两个数p和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.

我知道，要跟踪的数字很多。 但是，我们只需要关注最后两个数字p和q 。 因为根据RSA的密钥生成算法 ，如果我们知道e ， p和q ， 我们可以重新创建私钥。

“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?”

一个人可能会说：“很好，很完美。” “由于拥有公钥，因此我们知道e和N。 而且由于我们知道N ，我们只需要将其分开即可得到p和q 。 那有多难？”

Not so fast, person I just made up to ask loaded questions — p and q are prime numbers. Gasp!

没那么快，我刚刚问的很多问题— p和q是质数。 喘气！

I mentioned before that detecting if a number is prime is hard. What’s even harder is prime factorization.

我之前提到过很难检测数字是否为质数。 最困难的是素因数分解 。

How hard, you might ask?

您可能会问有多难？

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.

RSA通常使用1024、2048或3096位长的数字。 正如您在上图中所看到的，创建N只需几秒钟到几分钟，但将其分解需要数百万到数十亿年的时间。

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.

尽管这并非不可能，但付出的努力是天文数字，并不值得。 当我们能够生成Medium的私钥时，我们所有人早已死了。

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.

而且，如果您想知道，从本文开始的素数就不是素数。