1 cryptography

1.1 background

Privacy-preserving Computation refers to a series of information technologies that analyze and compute data on the premise that data providers do not disclose the original data, so as to ensure that data is not visible in the process of circulation and fusion. Gartner’s 2021 Frontier Technology Strategy Trends lists private computing (which it calls privacy-enhanced computing) as one of nine trends in technology over the next few years. (The need for data flows is driving the momentum for private computing.) But many obstacles remain.

The year 2021 is known as the first year of private computing. This technology is a very comprehensive field, involving many directions, such as cryptography, mathematics, big data, real-time computing, high-performance computing, distribution, traditional machine learning frameworks and algorithms, deep learning frameworks and algorithms, etc. This series of articles focuses on the use of cryptography for privacy computing.

1.2 Introduction to cryptography

Cryptography plays an important role in the whole process of human history, covering all aspects of human activities. For example, in spy movies, we often see that underground workers use encrypted messages to transmit important information. For example, TLS/SSL also protects our information security when surfing the Internet. It can be said that cryptography has far-reaching influence on human beings, and it is hard to imagine what life would be like without cryptography protection. So what exactly is cryptography? How exactly do you define cryptographic learning? This series of articles will provide a relatively detailed introduction. You are welcome to check it out.

First of all, the precise definition of cryptography or citing the authority, the following content from Baidu Encyclopedia:

Cryptography (in Western European languages, from the Greek kryptos, “to hide,” and graphein, “to write”) is the study of how to convey information secretly. In modern times, it refers especially to the mathematical study of information and its transmission. It is often regarded as a branch of mathematics and computer science, and information theory is also closely related. “Cryptography is about communicating in the presence of the enemy,” explains Ron Rivest, a renowned cryptographer. From an engineering point of view, this is the equivalent of the similarities and differences between cryptography and pure mathematics. Cryptography is at the heart of information security related issues such as authentication and access control. The primary purpose of cryptography is to hide the meaning of information, not its existence. Cryptography has also advanced computer science, particularly in the use of computer and network security techniques such as access control and information confidentiality. Cryptography is already used in everyday life, including chip cards for automated teller machines, access codes for computer users, e-commerce and more.

The cipher is an important secret means for communication parties to carry out special information transformation according to the agreed rules. According to these laws, the change of plain text into ciphertext, called encryption transformation; The transformation of ciphertext into plaintext is called densification transformation. In the early days of cipher, only text or digital are added and deencrypted. With the development of communication technology, voice, image and data can be added and deencrypted.

Cryptography was originally used to protect communication security in the presence of malicious attackers, but now it is the core technology used to protect information security.

Basic requirements of modern information security:

• Confidentiality of information: To prevent disclosure of information to unauthorized parties (encryption and decryption technology)
• Information Integrity: Preventing unauthorized tampering of information (message authentication code, digital signature)
• Authentication: To ensure that the message comes from the correct sender (message Authentication code, digital signature)
• Non-repudiation: guarantee that senders cannot repudiate messages they have sent (digital signature)

1.3 Cryptography terminology

• Key: includes encryption key and decryption key.
• Plaintext: unencrypted information that directly represents the meaning of the original text.
• Ciphertext: Hides the meaning of the original text after encryption.
• Encryption: The process of converting plain text into ciphertext.
• Decryption: The process of converting ciphertext into plaintext.
• Cryptography algorithm: encryption method and decryption method used by cryptography system. With the development of mathematical cryptography technology, encryption method is generally called encryption algorithm, and decryption method is generally called decryption algorithm.
• Encryption: The process of converting plain information (plaintext) into hard-to-understand data (ciphertext);
• Decryption algorithm is the opposite process: from ciphertext back to plaintext; Encryption and decryption includes these two algorithms. General encryption is the technology of simultaneously referential encryption (encrypt or Encipher) and decrypt (Decrypt or Decipher).

The specific operation of encryption and decryption is determined by two parts:

One is the algorithm, the other is the key. A key is a secret parameter used in encryption and decryption algorithms, usually owned only by the communicator.

1.4 Common schools of algorithms in modern cryptography

In time division, 1976 years ago cryptographic algorithms belong to the classical cryptography, basic use in the field of military secrets and diplomacy, its characteristic is to add the decryption process is simple, usually by hand or machine can be completed, classical cryptography is now rarely used, the following is a classical encryption password, provide one-to-one mapping transformation, With this password, you can easily encrypt and decrypt information through manual means.

The common encryption algorithms in modern cryptography can be roughly divided into the following types:

1. Hash algorithm: MD5 algorithm, Sha algorithm;
2. Symmetric encryption: DES, 3DES, RC2, RC4, AES, etc.
3. Asymmetric algorithms: RSA, ECC, etc.

This series of articles will focus on Diffie – Hellman Key Exchange, the first method of asymmetric encryption. This article relates to the mathematics of number theory related knowledge, for encryption algorithm will use knowledge, this chapter will do some appropriate introduction, students interested in number theory can refer to the relevant “number theory” books to improve, if there is no rigorous derivation, welcome students to help correct.

2 Basis of number theory

Before the formal introduction of RSA algorithm, because the algorithm needs more mathematical knowledge, is the so-called “great oaks grow from little acorns”, so according to the following steps to explain.

First of all, I will introduce the basic knowledge of number theory, including prime number, mutual prime relation, Euler function, Euler theorem and modular inverse elements. Then, will introduce the specific implementation process of RSA algorithm, and will be combined with examples to describe the theory and practice.

Then, according to the number theory, RSA algorithm security verification and derivation verification.

Finally, through this series of description and explanation, I believe that readers have mastered the RSA algorithm, and the application in network transmission will be introduced later.

Therefore, this section mainly introduces the basic knowledge of number theory to provide a theoretical basis for the derivation and proof of RSA algorithm.

2.1 prime Numbers

Prime numbers are a magical number in mathematics, and many mathematical theorems are based on them.

A natural number greater than 1 that is not divisible by any other natural number except 1 and the number itself (also defined as a number that has only two positive factors, 1 and the number itself). Natural numbers greater than 1 that are not prime are called composite numbers (also called composite numbers). For example, 5 is prime because its positive divisor is only 1 and 5. 6 is a composite number because 2 and 3 are positive divisor numbers as well as 1 and 6.

The fundamental theorem of arithmetic establishes prime numbers at the heart of number theory: any integer greater than 1 can be represented as a product of a series of unique prime numbers. To ensure the uniqueness of the theorem, 1 is defined as not a prime number, since there can be any number of 1’s in the factorization (e.g., 3, 1×3, 1×1×3, etc. are valid factorization of 3).

2.2 Mutual Prime Relation (Mutual prime Number)

If the common divisor of two integers is only 1, it is called a prime integer. Two natural numbers whose common divisor is only 1 are called mutually prime natural numbers, the latter being a special case of the former.

Such as:

1. 8.10The greatest common factor of PI is PI2, not1, so it is not integer interprime.2. 7.11.13The greatest common factor of PI is PI1So this is integer mutual quality.3. 5and5It's not quality because5and5The common factors of phi are1,5.4. 1It is multifold with any number, but it is interchangeable with any number.Copy the code

To sum up, mutual relations have the following properties

1.Two different primes must be mutually prime. For example,2with7.13and19.2.If one number is prime and the other number is not a multiple of it, the two are mutually prime, for example5and26.3.If the larger of the two numbers is prime, the relationship between the two numbers is mutual, for example97and57.4. 1It is neither prime nor composite, and is the same as any natural number (1Except itself) together are mutually beneficial. Such as1and9908.5.Two adjacent natural numbers are mutually prime. Such as15with16.6.Two odd numbers adjacent to each other are prime. Such as49with51.7.The two numbers whose larger numbers are prime are mutually prime. Such as97with66.Copy the code

2.3 Euler function

Euler (April 5, 1707 — September 18, 1783) was the son of a priest near Basel, Switzerland. He studied mathematics as well as theology and achieved great success. He is considered by some historians of mathematics to be one of the two greatest mathematicians in history (the other being Carl Friedrich Gauss). Many nouns in mathematics are named after Euler, such as Euler constant, Euler equation, Euler identity, Euler suggestive number and so on.

Euler is recognized as one of the most accomplished mathematicians in human history. Many of euler’s constants, formulas, and theorems can be found in mathematics and in many branches, and his work brought mathematics closer to its present form. He not only made contributions to mathematics, but also pushed mathematics to almost the entire field of physics. Euler was also involved in architecture, ballistics, navigation and other fields. Charles Kleiber, Switzerland’s secretary of state for Education and Research, has said: “Without Euler’s many scientific discoveries, we would be living a very different life today.” Laplace, the French mathematician, said: Read Euler. He is everyone’s teacher.

So in number theory, for the positive integer n, the euler function φ(n) calculation logic is the number of positive integers less than n that are mutually prime with n.

For example, in the1to8, and8What forms a reciprocal relationship is1,3,5,7, so φ(n) =4.Copy the code

1. If n is prime, then φ(n) =n-1. Conversely, if n is a positive integer and φ(n) =n-1, then n is prime.
2. If n is a prime number p k to the power, then the ϕ (pk) = 1 \ pk – pk – phi (p = p ^ ^ k) k – p ^ {1} k ϕ (pk) = pk – pk – 1.
3. If m and n are relatively prime Numbers, then ϕ (mn) = ϕ (m) ∗ ϕ (n) \ phi (mn) = \ \ phi phi (m) * (n) ϕ (mn) = ϕ (m) ∗ ϕ (n).
4. If n = p1a1 ∗ p2a2 ∗… ∗ pnann = p_1 ^ {a_1} * p_2 ^ {a_2} *… * p_n ^ {a_n} n = p1a1 ∗ p2a2 ∗… ϕ(n)=n(1−1p1)∗(1− 1P2)∗… ∗ (1-1 pn) \ phi (n) = n (1 – \ frac {1} {p_1}) * (1 – \ frac {1} {p_2}) *… * (1 – \ frac {1} {p_n}) ϕ (n) = n (1 – p11) ∗ (1 – p21) ∗… ∗ (1 – pn1).

2.4 Euler’s Theorem

Above we introduced prime numbers, interprime relations and Euler functions, based on this knowledge, we continue to introduce Euler’s theorem,

• define

If two positive integers A and n are mutually prime, then the Euler function φ(n) of n allows the following equation to be true, which can be understood as the remainder of a to the power φ(n) divided by n is 1.

A ϕ(n)≡1(mod n)a^{\phi(n)} \equiv 1(mod \; N) a ϕ (n) ≡ 1 (modn)

In layman’s terms, a ϕ(n)\phi(n)ϕ(n) divided by n has a remainder of 1, or a’s ϕ(n)\phi(n)ϕ(n) plus 1 is divisible by n.

• The sample

The positive integers 3 and 8 are mutually prime, where the euler function of 8 is 4 (the prime numbers are 1, 3, 5, 7), so 3 to the fourth power is 81,81 minus 1 is exactly 80, and 80 divided by 8 is exactly divisible.

• Special case: Fermat’s little theorem

Assuming that positive integer A and prime p are mutually prime, since φ(p) of prime P is equal to p-1, Euler’s theorem can be written

Ap −1≡1(mod n)a^{p-1} \equiv 1(mod \; 1 (modn) ≡ 1 n) ap –

Or you could write it as

Ap ≡a(mod n)a^{p} \equiv a(mod \; Ap ≡ n) a (modn)

Euler’s theorem (prove fermat’s little theorem) involved when the mould is sum Numbers (primes is fermat’s little theorem) how to deal with the specific congruence type, contains the index related to prove that you can see the number theory books, recommended reading “the machine of elementary number theory and its application” (Kenneth h. Rosen), the inside of the explanation is clear.

2.5 Modular inverse elements (modular inverse operation)

• define

The modular inverse element, also known as the modular inverse operation, is defined as follows: If two positive integers A and n are mutually prime, then the integer B must be found such that ab-1 is divisible by n, or the remainder of ab divided by n is 1. B is then called the modular antielement of A.

A ∗ b (mod n) ≡ 1 a * b \ equiv 1 (mod \; N) ≡ 1 a ∗ b (modn)

• The sample

For example, if 3 and 14 are mutually prime, then the modular inverse of 3 is 5, because 3 times 5 minus 1 is divisible by 14. Of course, there is more than one modular antielement, and the integer multiples of 5 plus or minus 14 are all modular antielements of 3 {… ,-23, -9, 5, 19, 33… }, that is, if b is modular antielement of A, then b+ kN are modular antielements of A.

2.6 the original root

Primal roots are a very important concept in number theory, especially in division theory.

! [image – 20220412173743076] (/ Users/dubaokun/Desktop / 1-1 – experience growth/post/work / 8 picture/article/image – 20220412173743076. The PNG)

For two mutually positive integers A and n. According to euler’s theorem, there are positive integers D ≤m− 1D \leq m-1D ≤m−1, such as the Euler function d=ϕ(n)d= phi(n)d=ϕ(n), that is, the number of positive integers less than or equal to M that are mutually essential to M, Makes AD ≡1(mod n)a^d \equiv 1(mod \; N) AD (modn) ≡ 1.

Thus, for two mutually positive integers A and n. The exponent δn(a)\delta_n(a)δn(a) is defined as such that AD ≡1(mod n)a^d equiv 1(mod \; N) AD ≡1(MODN) the smallest positive integer D true. By know the delta front n \ delta_n (a) (a) the delta n (a) must be less than or equal to ϕ (n) \ phi ϕ (n) (n), if the delta n (a) = ϕ (n) \ delta_n (a) = \ phi delta n (n) (a) = ϕ (n), says a is the root of n.

For example:

Given n=7, ϕ(n)\phi(n)ϕ(n) equals 6.

• Set a = 2, because 21 ≡ 2 (mod 7), 22 (mod 7) ≡ 4, 23 (mod 7) ≡ 1, 24 (mod 7) ≡ 2, 4 (mod 7) ≡ 25, 26 (mod 7) ≡ 1 2 ^ 1 \ equiv 2 (mod \; 7), 2^2\equiv 4(mod \; 7), 2^3\equiv 1(mod \; 7), 2^4\equiv 2(mod \; 7), 2^5\equiv 4(mod \; 7), 2^6\equiv 1(mod \; 7)21≡2(mod7), 22≡4(mod7), 23≡1(mod7), 24≡2(mod7), 25≡4(mod7), 26≡1(mod7), Hence the Ord7 (2) = 3 indicates ϕ (7) Ord_7 (2) = 3 \ neq \ phi (7) Ord7 (2) = 3  = ϕ (7), so 2 is not a primitive root module 7.
• Set a = 3, then because ≡ 3 (mod 7), 31, 32, 2 (mod 7) ≡ 33 ≡ 6 7 (mod), 34 (mod 7) ≡ 4, 35 ≡ 5 7 (mod), 36 (mod 7) ≡ 1 3 ^ 1 \ equiv 3 (mod \; 7), 3^2\equiv 2(mod \; 7), 3^3\equiv 6(mod \; 7), 3^4\equiv 4(mod \; 7), 3^5\equiv 5(mod \; 7), 3^6\equiv 1(mod \; 7)31≡3(mod7), 32≡2(mod7), 33≡6(mod7), 34≡4(mod7), 35≡5(mod7), 36≡1(mod7), Hence the Ord7 (3) = 6 = ϕ (7) Ord_7 (3) = 6 = \ phi (7) Ord7 (3) = 6 = ϕ (7), so 2 is not a primitive root module 7.

3 Diffie – Hellman key exchange

3.1 Diffie-Hellman Key Exchange Definition

Diffie-hellman Key Exchange is a security protocol. It allows each party to create a key over an unsecured channel without any prior information about the other. This key can be used as the content of symmetric secret key message in subsequent communication. The concept of public key exchange was first proposed by Ralph C. Merkle, and this key exchange method was first published by Bailey Whitfield Diffie and Martin Edward Hellman in 1976. Martin Hellman has argued that this key exchange method should be called Diffie – Hellman – Merkle key Exchange.

Although defy-Hermann key exchange itself is an anonymous (unauthenticated) key exchange protocol, it is the basis for many authentication protocols.

3.2 Protocol History

The Diffe-Hermann key exchange was developed in collaboration with American cryptographers Whitfield Diffey and Martin Hermann and published in 1976. It is the first practical method for creating a shared key in an unprotected channel. It was influenced by The work of Ralph Mork on public key allocation. John Gill proposed an application of the discrete logarithm problem. The scheme was first developed by Malcolm J. Williamson in Britain a few years earlier, but GCHQ didn’t decide to publish it until 1997, when there was no academic buzz about the algorithm.

Not long after this method was invented came RSA, another algorithm for public key exchange. It uses asymmetric encryption algorithms.

In 2002, Martin Herman wrote:

The system… It has since been called the diffie – Hermann key Exchange. Although this system was first described in a paper by Me and Diffie, it is a public key exchange system, a concept developed by Merke, so if his name is added, the system should actually be called Diffie — Hellman — Merkle key exchange. I hope this small forum will help us recognize merke’s equally important contribution to public key cryptography.

The system… Has since become known as Diffie — Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, And hence should be called ‘Diffie — Hellman — Merkle key exchange’ if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle’s equal contribution to the invention of public key cryptography.

U.S. patent No. 4,200,770, which describes the algorithm, expired after April 29, 1997, and identifies Hellman, Diffie, and Merkle as the inventors of the algorithm.

3.3 Algorithm protocol flow

By exchanging a message over a public channel, Diffier-Hellman can create one that can be used to communicate securely over a public channel.

Here’s how it works (including the math part of the algorithm) :

The simplest and earliest proposed protocol uses the integer modulo n multiplicative group of a prime number P and its primitive root G. The algorithm is shown below, with non-secret information in green and secret information in bold red:

As you can see from the flow above, Alice and Bob both end up with the same value because gab and gbag^{ab} and G ^{ba}gab and GBA are equal in the case of modular P. Note that A, b and gab=gbamodpa, b and g^{ab}=g^{ba} mod Pa, b and gab=gbamodp are secret.

So once Alice and Bob have the common key, which is 2 above (which of course is not the case), they can use the public key for symmetric encryption. Because only they have access to this secret key. Of course, to make this example more secure, you must use very large a, b and PA, b and pa, b and P, otherwise you can brute force, such as gabmod23g^{ab} mod 23gabmod23, there are only 22 such values, even if a and B are large. If p is a prime number with at least 300 digits, and a and B are at least 100 digits long, then even the best available resources and algorithms cannot compute a from G, p and gamodpg, p and g^{a} modpg, p and GAModp. This is the famous discrete logarithm problem, Interested readers can check this out. It is also important to note that g does not have to be large, in practice it is usually 2 or 5. Several commonly used large prime numbers are available in the IETF RFC3526 document.

3.4 Security verification of algorithmic protocols

The following illustration will help you understand who only knows each piece of information. Eve is an eavesdropper — she can see Alice and Bob’s communications, but can’t change them.)

• Let s = shared key. s = 2

• Let a = Alice’s private key. If a = 6

• Let A = Alice’s public key. For example A = ga mod p = 8

• Let b = Bob’s private key. If b = 15

• Let B = Bob’s public key. B = GB mod P = 19

• Let g = common primitive root. Such as g = 5

• Let p = common prime. Such as p = 23

! [image – 20220412170926559] (/ Users/dubaokun/Desktop / 1-1 – experience growth/post/work / 8 picture/article/image – 20220412170926559. The PNG)

Note: it should be difficult for Alice to unlock Bob’s private key or for Bob to unlock Alice’s private key. If it wasn’t hard for Alice to unlock Bob’s private key (and vice versa), Eve could easily replace her own private/public key pair, insert Bob’s public key into her own private key, generate a fake shared key, and unlock Bob’s private key (and use this to unlock the shared private key). Eve can try to choose a public/private key pair that will allow her to easily unlock Bob’s private key.

Iv Reference Materials

• Zh.wikipedia.org/wiki/%E5%8E…
• En.wikipedia.org/wiki/Diffie…

Five set pieces

Personal Introduction: Du Baokun, a practitioner in the privacy computing industry, led the team to build JD’s federal learning solution 9N-FL from 0 to 1, and led the federal learning framework and federal start-up business. Framework level: realized the industrial federated learning solution supporting super-large scale in the field of e-commerce marketing, and supported many models such as super-large sample PSI privacy alignment, tree model and neural network model. Business level: achieved a good start in business, created new business growth points and generated significant business economic benefits. Personally, I like to learn new things and delve into technology. Based on the consideration of full-link thinking and decision technology planning, there are many research fields, ranging from engineering architecture, big data to machine learning algorithms and algorithm frameworks. Welcome students who like technology to communicate with me, email: [email protected]

The guide of the official account

I have been writing my blog for a long time. I have been involved in many technical fields, such as high concurrency and high performance, distributed, traditional machine learning algorithms and frameworks, deep learning algorithms and frameworks, password security, private computing, federated learning, big data and so on. I have led a number of major projects, including retail federation learning, community sharing for many times. In addition, I insist on writing original blog, and many articles have been read by thousands of people. Public number bald code farmers we can continue to read in accordance with the topic, which I have done in accordance with the order of the learning route, the topic is the public number inside the following marked red this, you can click to see the topic under the article, such as the following figure (topic is divided into: (1) Private computing (2) Federated learning (3) Machine learning frameworks (4) Machine learning algorithms (5) High performance computing (6) Advertising algorithms (7) Procedural Life (7).

All promising dharma, like a dream, like dew, like electricity, should be viewed as such.