本文共 12899 字，大约阅读时间需要 42 分钟。
移位密码和乘法密码
All around us data is transferred faster than ever. Sensitive data is also part of our everyday life. To protect that data, we use encryption. When we encrypt data, it changes in some way that renders it useless to the possible viewer, but that can be changed back to its original state when it arrives safely to the meant receiver. These transformations rely heavily on math, and particularly on a field of math called number theory. This text takes us through the basics of cryptography both from a mathematical perspective and as a programming matter.
我们周围的数据传输比以往任何时候都快。 敏感数据也是我们日常生活的一部分。 为了保护该数据，我们使用加密。 当我们加密数据时，它会以某种方式改变，使可能的查看者无法使用它，但是当数据安全地到达目标接收者时，可以更改回其原始状态。 这些转换严重依赖于数学，尤其是依赖于称为数论的数学领域。 本文从数学角度和编程方面带我们了解了密码学的基础知识。
For as long as writing has existed, the concept of encryption has lived and developed alongside the plain text writing. The idea of rendering text seemingly incomprehensible for purposes of guarding a secret has been central especially in military use and politics. The word cipher originates from the medieval times, from words such as the latin cifra and Arabic صفر (sifr), which means “zero”. There are numerous theories on why zero would have been used to describe encryption, including that the concept of zero was not part of the roman number system and seen as a mystery among numbers. One of the oldest and most widely known ciphers used in military context is Caesars cipher, also known as Caesars shift.
只要存在书写，加密的概念就与纯文本书写一起存在和发展。 出于保护秘密的目的，呈现文本似乎难以理解的想法一直很重要，尤其是在军事用途和政治领域。 密码一词起源于中世纪，起源于拉丁语cifra和阿拉伯语صفر (sifr)，表示“零”。 关于为什么使用零来描述加密有很多理论，包括零的概念不是罗马数字系统的一部分，被视为数字之间的一个谜。 在军事环境中使用的最古老和最广为人知的密码之一是凯撒密码，也称为凯撒移位。
Caesars shift takes one key, which is used to shift each character in the plaintext. This single key is the weakness of the cipher: once the correct shift is figured out, the whole message is revealed. Mathematically, this type of cipher can be written as a problem in modular arithmetic, which works with values wrapped up in a specific range. We’ll discuss this in more depth later.
凯撒平移需要一个键，该键用于平移明文中的每个字符。 这个唯一的密钥就是密码的弱点：一旦找出正确的移位，整个信息就会被揭示出来。 从数学上讲，这种类型的密码可以写为模数运算中的问题，它适用于在特定范围内包装的值。 稍后我们将对此进行更深入的讨论。
The way we can solve the plaintext from the encrypted text is by finding the key. In the case of a Caesars cipher of value 3, finding out the key (3) lets us decrypt the whole text in one chunk. The key specifies the output of the encryption algorithm.
我们可以通过找到密钥来从加密的文本中解析纯文本的方法。 在凯撒密码为3的情况下，找出密钥(3)可让我们将整个文本解密为一个块。 密钥指定加密算法的输出。
Perhaps surprisingly, one of the foundational concepts that lays the ground for encryption is that of divisibility. To define what it means, let’s lay down some rules. Firstly, if we have a and b that are integers and a is not 0, a divides b if there is such an integer k that satisfies the following statement.
也许令人惊讶的是，为加密奠定基础的基本概念之一是可分割性。 为了定义含义，让我们制定一些规则。 首先，如果我们的a和b是整数，而a不为0，则如果存在满足以下语句的整数k ，则a除以b 。
In case we find an integer which is larger than 1 and that does not have other positive factors than 1 and itself, we call it a prime. Integers larger than one which are not primes are known as composite numbers, due to their composed nature. For example, 4 is larger than 1 and it has a factor 2. Hence, it is a composite. On the other hand, 3 is an integer larger than one, but it does not have any other positive factors than 1 and itself. It is a prime. Other small primes are 2, 5, 7, 11 and 13.
如果我们发现一个大于1的整数，并且没有除1及其本身之外的其他正数，我们称其为质数 。 大于整数(不是素数)的整数由于其组成性质而被称为复合数 。 例如，4大于1且具有因子2。因此，它是一个复合。 另一方面，3是大于1的整数，但除1及其本身外，没有其他任何正数。 这是素数。 其他小的素数是2、5、7、11和13。
According to the fundamental theorem of arithmetic, every integer larger than 1 can be written as an unique product of primes. This is good news for cryptographers, since they love working with primes. Why would that be? Well, one of the most straightforward reasons is that prime factorisation of large numbers takes up a lot of time. Many well known encryption systems such as RSA is fully based on this fact. The principal it works on is that there exists a public key (a product of two large primes) which is used to encrypt the message, and a secret key (containing those primes) which is used to decrypt the message. These primes are usually around 300 digits long.
根据算术的基本定理，每个大于1的整数都可以写为素数的唯一乘积。 对于密码学家来说，这是个好消息，因为他们喜欢使用素数。 为什么会这样呢？ 好吧，最直接的原因之一是大量素数分解需要大量时间。 许多众所周知的加密系统(例如RSA)完全基于此事实。 它的工作原理是，存在一个用于加密消息的公用密钥(两个大素数的乘积)，和一个用于解密消息的秘密密钥(包含那些素数)。 这些素数通常约为300位数长。
Modularity is one of the foundational pillars of cryptography. Let’s approach this concept first from a perspective of division. What happens if we have 5 small candies and three students? Each student gets a candy, and 2 remain. This can be described as the following.
模块化是密码学的基础Struts之一。 让我们首先从分裂的角度来探讨这个概念。 如果我们有5个小糖果和3个学生，将会怎样？ 每个学生得到一个糖果，剩下2个。 可以描述如下。
Can you find the other amounts of candies which leave 2 as a remainder when divided to the 3 students? The next amount would be 8, since each student would get two candies and again 2 would be left over. This can be described using congruence. 8 and 5 are congruent is modulo 3, meaning that they leave the same remainder when divided by 3.
您能否找到分配给3个学生的剩余2个糖果的剩余数量？ 下一个数量将是8，因为每个学生将获得两个糖果，然后再剩下2个。 这可以用全等描述。 8和5是模3的全等，这意味着当它们除以3时它们将保留相同的余数。
In the example of Caesars shift, we use an alphabet that consists of 26 letters. We only work with those 26 values. After ‘Z’, we go back to ‘A’. This is modularity in practice. ‘A’ will always be at position 1 in our 26-letter list, so any count of position we get, if we divide it by 26 and the remainder is 1, we know to use ‘A’. This wraps up our numbers into a finite field, in which the largest value is 26. In practice, if my secret message would be ‘ABC’, I would first convert this to the numbers 123. After that, I would apply the shift. In case the key would be 3, the shift would produce 456. After this, I would point the numbers back to their letter representations, which are in the class of modulo 26. The encrypted message becomes ‘DEF’.
在凯撒平移的示例中，我们使用由26个字母组成的字母。 我们仅使用这26个值。 在“ Z”之后，我们回到“ A”。 这实际上是模块化。 “ A”将始终位于26个字母的列表中的位置1，因此，如果将其除以26，而余数为1，则我们得到的任何位置计数都知道使用“ A”。 这会将我们的数字包装到一个有限的字段中，其中的最大值是26。实际上，如果我的秘密消息是“ ABC”，我首先将其转换为数字123。此后，我将应用移位。 如果密钥为3，则移位将产生456。此后，我将数字指向它们的字母表示形式，该类型属于模26。加密的消息变为“ DEF”。
You can think of this like a clock. When the arrow has gone around the clock, it ends up where it started. In modular arithmetics, the last integer is followed by the first. Another way to understand this is that the world of a specific modulo, only that amount of values exist. For example in modulo 2, only 2 values exist. In our alphabet, 26 values exist, and so on.
您可以将其视为时钟。 箭头不停地移动时，它会从其开始处结束。 在模块化算术中，最后一个整数后面是第一个整数。 理解这一点的另一种方式是，特定模数的世界仅存在一定数量的值。 例如，在模2中，仅存在2个值。 在我们的字母中，存在26个值，依此类推。
What kind of keys a cipher uses can be used to categorise the cipher into asymmetric and symmetric keys. They differ in the question of which key is used for encryption and decryption. Symmetric ciphers are encrypted and decrypted using the same key (such as Caesars Cipher). Asymmetric key ciphers are decrypted with a different key than they are created with, such as the RSA encryption system which we briefly discussed earlier. This results in a longer time for creating the encryption, but the result is also much more secure.
密码使用哪种密钥可用于将密码分为非对称密钥和对称密钥。 它们的区别在于哪个密钥用于加密和解密。 对称密码使用相同的密钥(例如Caesars Cipher)进行加密和解密。 非对称密钥密码使用与创建密钥不同的密钥解密，例如我们前面简要讨论过的RSA加密系统。 这样会导致创建加密的时间更长，但结果也更加安全。
Another way to categorise ciphers is by their way of operating in streams or blocks. Stream ciphers are symmetric key ciphers that operate on continuous streams of symbols. For example the encryptions used in Bluetooth is a stream cipher. Needless to say, in the age of wireless communication with a need for encryption, stream ciphers have become a vital part of mobile technology.
对密码进行分类的另一种方法是通过它们以流或块的方式进行操作。 流密码是对连续符号流进行操作的对称密钥密码。 例如，蓝牙中使用的加密是流密码。 毋庸置疑，在需要加密的无线通信时代，流密码已成为移动技术的重要组成部分。
Remember that we discussed the concept of modular arithmetic earlier? In short, modular arithmetics are arithmetics in a finite field. Now, let’s take a look at another cipher that works with a finite field of values (also known as a Galois field). This cipher, however, does not always produce the same values given the same input, like shifting does. Its purpose is to produce a stream of keys used to encrypt another stream. Like a snake eating its own tail (a symbol often used for eternity), linear feedback shift registers work by feeding on their own output. They are constructed in a way that makes them endlessly cycle through a pattern of values while outputting that seemingly random pattern. The seed and all the outputted values are binary, meaning they get values 0 or 1. The way new values are created is by using a logical operator, usually exclusive or (XOR).
还记得我们之前讨论过模块化算术的概念吗？ 简而言之，模块化算术是有限域中的算术。 现在，让我们看一下适用于有限值字段(也称为Galois字段)的另一种密码。 但是，给定相同的输入，此密码并不总是像移位一样产生相同的值。 其目的是产生用于加密另一个流的密钥流。 就像一条蛇吃着自己的尾巴(常用于永恒的符号)一样，线性反馈移位寄存器通过馈送自己的输出来工作。 它们的构造方式使它们在输出看似随机的模式的同时不断地循环通过值的模式。 种子和所有输出值都是二进制的，这意味着它们获得的值为0或1。创建新值的方式是使用逻辑运算符，通常是“异或”或(XOR)。
To describe this in a practical way, lets start looking at what we need to create a LFSR. We need a seed, which is a list of ones and zeros. The seed will be what we start shifting. In addition to our seed (or shift register) we have a collection of taps. The taps tell us which parts of the register we use when feeding back into it. Say that we have a seed 001 and two taps, 1 and 3. This means that when we start shifting, the new value will be a combination of the first and third numbers of the seed, 0 and 1. We use an operation called exclusive or to combine the two. 0 xor 1 gives 1. Since we are working with binary values, the feedback from our taps can be expressed as a polynomial in modulo 2.
为了以实际的方式进行描述，让我们开始研究创建LFSR所需的内容。 我们需要一个种子，它是一和零的列表。 种子将是我们开始转移的东西。 除了种子(或移位寄存器)之外，我们还有水龙头的集合。 水龙头告诉我们在将寄存器反馈给寄存器时，我们使用寄存器的哪一部分。 假设我们有一个种子001和两个抽头1和3。这意味着当我们开始移位时，新值将是种子的第一个数字和第三个数字0和1的组合。我们使用称为互斥的操作或结合两者。 0 xor 1给出1。由于我们在处理二进制值，因此抽头的反馈可以表示为模2的多项式。
So, if our shift register is 001 and we get a new value, 1, we insert it in the beginning and drop the last number out. Our new shift register state is now 100. We continue this shifting until we notice that our shift register has returned to it’s initial state, 001. Depending on the seed and taps we select, we can get loops of different lengths. A loop is called maximal length if it passes through all possible different combinations before reaching its original state. Since we’re using the binary system, the maximal length of a loop will be 2^n-1. The loop can also end up leaving its original state and getting stuck in a shorter loop within, never returning to its original state. Finding the seeds and taps that lead to a maximal-length cycle is essential. Some of the criterions for finding these taps is that the number of taps must be even and that the taps are setwise co-primes, meaning that they have no common divisor except 1.
因此，如果我们的移位寄存器为001并且得到一个新值1，则将其插入开头并删除最后一个数字。 现在，我们的新移位寄存器状态为100。我们继续进行此移位，直到我们注意到移位寄存器已返回其初始状态001。根据选择的种子和抽头，我们可以获得不同长度的循环。 如果循环在到达其原始状态之前经过所有可能的不同组合，则称为最大长度 。 由于我们使用的是二进制系统，因此循环的最大长度为2 ^ n-1。 该循环还可能最终离开其原始状态，并陷入一个较短的循环中，而永不返回其原始状态。 找到导致最大长度循环的种子和水龙头至关重要。 查找这些抽头的一些标准是，抽头的数量必须是偶数，并且这些抽头是按设定的互素数，这意味着它们除1以外没有其他除数。
Wait, that doesn’t seem so random! Wouldn’t a cycle like that be pretty easy to crack? The thing about shift registers is that they get pretty long, pretty quickly. Say we choose a seed of 20 bits and a tap of two values, 2 and 19. The length of the loop produced is 1 048 575, meaning we would get quite a large amount of seemingly random binary values.
等等，这似乎不是那么随意！ 这样的循环难道不容易破解吗？ 关于移位寄存器的事情是，它们变长，变快。 假设我们选择一个20位的种子，并选择两个值2和19的抽头。所产生的循环长度为1048575，这意味着我们将获得大量看似随机的二进制值。
The flavour of LFSR we have briefly gone through is called Fibonacci LFSR. There are also other variations, in which the way the register is shifted differs. They all work to produce a pseudorandom stream of bits used to encrypt streams. The range of applications for this type of encryption ranges from bluetooth to GSM (cellphone communication) standards.
我们简要介绍过的LFSR的味道称为斐波那契LFSR。 还有其他变体，其中寄存器移位的方式不同。 它们全都产生用于加密流的伪随机位流。 此类加密的应用范围从蓝牙到GSM(手机通信)标准。
As a programmer, learning about the concept of modular arithmetics and division opens new ways in thinking about everyday coding problems. However, in security-critical projects using ready-made systems and standards for encryption is always recommended, since specialists in the field of cryptography probably find a safer and more effective solution than an enthusiastic hobbyist.
作为一名程序员，学习模块化算术和除法的概念为思考日常编码问题开辟了新途径。 但是，在安全性至关重要的项目中，始终建议使用现成的系统和加密标准，因为与热心的业余爱好者相比，加密领域的专家可能会找到更安全，更有效的解决方案。
Sources:
资料来源：
翻译自:
移位密码和乘法密码
转载地址：http://fezzd.baihongyu.com/