The rsa encryption algorithm is based on complexity. RSA encryption algorithm

RSA encryption is one of the first practical public key cryptosystems and is widely used for secure data transmission. Its main difference from similar services is that the encryption key is public and differs from the decryption key, which is kept secret. RSA technology is based on the practical difficulty of factoring two large prime numbers (the factoring problem).

History of creation

The name RSA is made up of the initial letters of the surnames of Rivest, Shamir and Adleman, the scientists who first publicly described these in 1977. Clifford Cox, an English mathematician who worked for the British intelligence services, first developed an equivalent system in 1973, but it was not declassified until 1997.

The RSA user creates and then publishes a public key based on two large prime numbers along with an auxiliary value. must be kept secret. Anyone can use a public key to encrypt a message, but if it is large enough, then only someone with knowledge of prime numbers can decode the message. Breaking RSA encryption is known to be a major problem: today there is an open debate about how secure the mechanism is.

RSA is a relatively slow algorithm, which is why it is not widely used by the direct user. The most common use of this method is to transmit encrypted shared keys for a symmetric encryption key, which in turn can perform bulk encryption and decryption operations at much higher speeds.

When did the cryptosystem appear in its modern form?

The idea of ​​an asymmetric key cryptosystem is attributed to Diffie and Hellman, who published the concept in 1976, introducing digital signatures and attempting to apply number theory. Their formulation uses a shared secret key created from the exponent of some number modulo a prime number. However, they left open the problem of implementing this function, since the principles of factoring were not well understood at that time.

Rivest, Adi Shamir, and Adleman at MIT made several attempts over the course of a year to create a one-way function that is difficult to decode. Rivest and Shamir (as computer scientists) proposed many potential functions, while Adleman (as a mathematician) searched for the algorithm's weaknesses. They took many approaches and eventually developed the final system in April 1977, today known as RSA.

Digital signature and public key

An electronic digital signature, or EDS, is an integral part of electronic documents. It is formed by a certain cryptographic change in data. Using this attribute, it is possible to check the integrity of a document, its confidentiality, and also determine who its owner is. Essentially, this is an alternative to the usual standard signature.

This cryptosystem (RSA encryption) offers a public key, which makes it different from symmetric ones. The principle of its operation is that two different keys are used - private (encrypted) and public. The first is used to generate an electronic signature and subsequently be able to decrypt the text. The second is for the actual encryption and verification of the digital signature.

Using a signature allows us to better understand RSA encryption, an example of which can be given as an ordinary classified “closed from prying eyes” document.

What is the essence of the algorithm?

The RSA algorithm consists of four stages: key generation, key distribution, encryption and decryption. As already stated, RSA encryption includes a public key and a private key. Open can be known to everyone and is used to encrypt messages. Its essence is that messages encrypted using a public key can only be decrypted within a certain period of time using a private key.

To be safe, the integers should be randomly selected and be the same in size, but vary in length by a few digits to make factoring more difficult. Identical numbers can be effectively found using a test for their primality, so encryption of information must necessarily become more complicated.

A public key consists of a modulus and a public exponent. Private consists of a module and a private indicator that must be kept secret.

RSA File Encryption and Weaknesses

However, there are a number of mechanisms for breaking simple RSA. When encrypting with low rates and small numbers, the cipher can be easily broken if you find the root of the ciphertext over the integers.

Because RSA encryption is a deterministic algorithm (i.e., it has no random component), an attacker can successfully launch a chosen plaintext attack against a cryptosystem by encrypting plausible plaintexts under the public key and checking to see if they are equal to the ciphertext. A cryptosystem is said to be semantically secure if an attacker cannot distinguish two encryptions from each other, even if he knows the corresponding texts in cleared form. As described above, RSA, without complementing it with other services, is not semantically secure.

Additional encryption and security algorithms

To avoid the above problems, practical implementations of RSA typically build in some form of structured, randomized padding before encryption. This ensures that the content does not fall within the range of insecure plaintext and that the message cannot be compromised by chance.

The security of the RSA cryptosystem and the encryption of information are based on two mathematical problems: the problem of factoring large numbers and the RSA problem itself. Full disclosure of ciphertext and digital signature in RSA is considered unacceptable on the assumption that both of these problems cannot be solved together.

However, thanks to the ability to recover prime factors, an attacker can calculate the secret exponent from the public key and then decrypt the text using a standard procedure. Although no existing method has been found today for factoring large numbers on a classical computer, it has not been proven that it does not exist.

Automation

A tool called Yafu can be used to streamline this process. Automation in YAFU is a state-of-the-art feature that combines factorization algorithms in an intelligent and adaptive methodology that minimizes the time to find factors of arbitrary input numbers. Most implementations of the algorithm are multi-threaded, allowing Yafu to take full advantage of multi or many (including SNFS, SIQS and ECM). First of all, it is a managed command line tool. The time spent searching for an encryption factor using Yafu on a regular computer can be reduced to 103.1746 seconds. The tool produces processing capacity of 320 bits or more. This is very complex software that requires a certain amount of technical skill to install and configure. Thus, RSA C encryption may be vulnerable.

Hacking attempts in modern times

In 2009, Benjamin Moody, using an RSA-512 bit key, worked to decrypt cryptotext for 73 days using only common software (GGNFS) and an average desktop computer (dual-core Athlon64 at 1900 MHz). As this experience showed, a little less than 5 gigabytes of disk and about 2.5 gigabytes of RAM were required for the “sifting” process.

As of 2010, the largest factored RSA number was 768 bits long (232 decimal digits, or RSA-768). Its deployment lasted two years on several hundred computers simultaneously.

In practice, RSA keys are longer - usually from 1024 to 4096 bits. Some experts believe that 1024-bit keys may become insecure in the near future, or may even already be cracked by a reasonably well-funded attacker. However, few would argue that 4096-bit keys can also be revealed in the foreseeable future.

Prospects

Therefore, RSA is generally assumed to be secure if the numbers are large enough. If the base number is 300 bits or shorter, the ciphertext and digital signature can be decomposed within a few hours on a personal computer using software that is already freely available. 512-bit keys were proven to be crackable as early as 1999 using several hundred computers. These days, this is possible within a few weeks using publicly available hardware. Thus, it is quite possible that in the future RSA encryption will be easily broken on the fingers, and the system will become hopelessly outdated.

Officially, in 2003, the security of 1024-bit keys was questioned. Currently it is recommended to be at least 2048 bits long.

Electronic digital signature (EDS) is a requisite of an electronic document intended to certify the source of data and protect this electronic document from forgery.

General scheme

An electronic signature scheme usually includes:

• algorithm for generating user key pairs;
• signature calculation function;
• signature verification function.

The function of calculating a signature based on the document and the user's secret key calculates the signature itself. Depending on the algorithm, the signature calculation function can be deterministic or probabilistic. Deterministic functions always compute the same signature from the same input data. Probabilistic functions introduce an element of randomness into the signature, which enhances the cryptographic strength of digital signature algorithms. However, probabilistic circuits require a reliable source of randomness (either a hardware noise generator or a cryptographically secure pseudo-random bit generator), which complicates implementation.

Currently, deterministic schemes are practically not used.

The signature verification function checks whether a given signature matches the given document and the user's public key. The user's public key is publicly available, so anyone can verify the signature on a given document.

Since the documents being signed are of variable (and quite large) length, in digital signature schemes the signature is often placed not on the document itself, but on its hash. Cryptographic hash functions are used to calculate the hash, which ensures that changes to the document are detected when the signature is verified. Hash functions are not part of the digital signature algorithm, so any reliable hash function can be used in the scheme.

Security

A digital signature provides:

• Identification of the source of the document. Depending on the details of the document definition, fields such as “author”, “changes made”, “time stamp”, etc. may be signed.
• Protection against document changes. Any accidental or intentional change to the document (or signature) will change the hash and therefore invalidate the signature.
• Impossibility of relinquishing authorship. Since you can create a correct signature only by knowing the private key, and it is known only to the owner, the owner cannot refuse his signature on the document.

The following digital signature threats are possible:

• An attacker may try to forge a signature for a document of his choice.
• An attacker may try to match a document to a given signature so that the signature matches it.
• An attacker may try to forge a signature for a document.

When using a reliable hash function, it is computationally difficult to create a counterfeit document with the same hash as the genuine one. However, these threats can be realized due to weaknesses in specific hashing or signature algorithms, or errors in their implementations.

However, the following threats to digital signature systems are also possible:

• An attacker who steals a private key can sign any document on behalf of the key owner.
• An attacker can trick the owner into signing a document, for example using a blind signature protocol.
• An attacker can replace the owner's public key (see key management) with his own, impersonating him.

Digital signature algorithms

• American electronic digital signature standards: DSA, ECDSA

• Russian standards for electronic digital signature: GOST R 34.10-94 (currently not valid), GOST R 34.10-2001
• Ukrainian standard for electronic digital signature: DSTU 4145-2002
• The PKCS#1 standard describes, in particular, an electronic digital signature scheme based on the RSA algorithm

Key management

An important problem in all public key cryptography, including digital signature systems, is public key management. It is necessary to ensure that any user has access to the true public key of any other user, protect these keys from being replaced by an attacker, and also organize the revocation of the key if it is compromised.

The problem of protecting keys from substitution is solved with the help of certificates. The certificate allows you to certify the data contained in it about the owner and his public key with the signature of any trusted person. Centralized certificate systems (such as PKI) use certificate authorities maintained by trusted organizations. In decentralized systems (for example PGP), by cross-signing certificates of familiar and trusted people, each user builds a network of trust.

Key management is handled by certificate distribution centers. By contacting such a center, the user can obtain a certificate for a user, and also check whether a particular public key has not yet been revoked.

Description of the RSA algorithm

RSA- public key cryptographic algorithm. RSA was the first algorithm of its type, suitable for both encryption and digital signature. The algorithm is used in a large number of cryptographic applications.

Story

British mathematician Clifford Cocks, working at the UK Government Communications Center (GCHQ), described a similar system in 1973 in internal GCHQ documents, but this work was not disclosed until 1977 and Rivest, Shamir and Adleman developed RSA independently of the work Cox.

US Patent 4,405,829 was issued to MIT in 1983 and expired on September 21, 2000.

Description of the algorithm

The security of the RSA algorithm is based on the difficulty of the factorization problem. The algorithm uses two keys - open (public) and secret (private), together the public and corresponding secret keys form a key pair (keypair). The public key does not need to be kept secret; it is used to encrypt the data. If a message was encrypted with a public key, it can only be decrypted with the corresponding private key.

Key generation

To generate a key pair, perform the following steps:

1. Two large prime numbers are selected and

2. Their product is calculated

3. The Euler Function is calculated

4. An integer is chosen such that and coprime with

5. Using the extended Euclidean algorithm, a number is found such that

The number is used as ciphertext. To decrypt, you need to calculate

It is easy to see that when decrypting we will restore the original message:

From the condition

follows that

for some integer, therefore

According to Euler's theorem:

Some features of the algorithm

Generating Prime Numbers

To find two large prime numbers and , when generating a key, probabilistic primality tests are usually used to quickly identify and discard composite numbers.

· with a small value of the open indicator (, for example), a situation is possible when it turns out that . Then the intruder can easily restore the original message by calculating the root of .

· since RSA is a deterministic algorithm, i.e. does not use random values ​​during operation, an attacker can use a chosen plaintext attack.

To solve these problems, messages are supplemented before each encryption with some random value - a salt. The padding is done in such a way as to ensure that , and . In addition, since the message is supplemented with random data, when encrypting the same plaintext we will receive a different ciphertext value each time, which makes a chosen plaintext attack impossible.

Selecting an open indicator value

RSA is significantly slower than symmetric algorithms. To increase encryption speed, the open exponent is chosen to be small, usually 3, 17 or 65537. These numbers in binary form contain only two ones, which reduces the number of necessary multiplication operations when raising to a power. For example, to raise a number to the power of 17, you need to perform only 5 multiplication operations:

should be big enough. In 1990, Michael J. Wiener showed that if you choose small, it turns out to be large enough and there is no problem.

Key length

Number n must be at least 512 bits in size. Currently, the RSA-based encryption system is considered strong starting with size N of 1024 bits.

Application of RSA

The RSA system is used for software security and in digital signature schemes. It is also used in the open encryption system PGP.

Due to the low encryption speed (about 30 kbps with a 512-bit key on a 2 GHz processor), messages are usually encrypted using higher-performance symmetric random key algorithms ( session key), and using RSA they encrypt only this key.

II. Implementation

As an example, a program was implemented for digitally signing files and verifying signatures. The RSA algorithm and X.509 certificates were used. The user certificate is selected from the windows certificate store.

Digital signatures are saved in an xml file with the name<имя исходного файла>.sig.xml

Code snippets

public class Signature

private X509Certificate2 certificate;

private DateTime date;

private byte signedHash;

public X509Certificate2 Certificate

get(return certificate;)

set (certificate = value; )

public DateTime Date

get(return date;)

set( date = value; )

public void Sign(string input, X509Certificate2 cert)

this.certificate = new X509Certificate2(cert);

date = DateTime.Now;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider());

public bool IsValid(string input)

string stringToEncrypt = input + date.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider(), signedHash);

public byte SignedHash

get (return signedHash; )

set ( signedHash = value; )

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach (Signature signaure in fileSignatures.Signaures)

string row = "";

row+= signaure.Certificate.Subject;

row+=" "+signaure.Date.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool valid = signaure.IsValid(hash);

row = "v " + row;

row = "x " + row;

signatureListTextBox.Text += row+"\r\n";

III. Literature

1. S. Burnet, S. Payne: Cryptography. Official RSA Security Guide – M. “Binom”, 2002
2. V. Winter: Security of global network technologies - “BHV-Petersburg”, 2003
3. Wenbo Mao Modern Cryptography: Theory and Practice = Modern Cryptography: Theory and Practice. - M.: "Williams", 2005. - P. 768. ISBN 0-13-066943-1
4. Nils Ferguson, Bruce Schneier Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - M.: "Dialectics", 2004. - P. 432. ISBN 0-471-22357-3
5. Schneier, Bruce. Applied cryptography. Protocols, algorithms, source texts in C language - M.: TRIUMPH Publishing House, 2002 - 816 pp.: ill. ISBN 5-89392-055-4

Let's consider the operation of an asymmetric RSA . It was proposed by three mathematicians Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) and Leonard Adleman ( L. Adleman) in 1978.

Under prime number We will understand a number that is divisible only by 1 and itself. Euclid in his Elements showed that for every prime number there is a greater prime number, that is, the number of prime numbers is infinite.

Proof. Suppose there is a greatest prime number p, we define the product of all prime numbers P=2∙3∙5∙7∙…∙p.

Consider the number P+1. It is either itself a large prime number p or the product of prime numbers that are greater P. We have come to a contradiction, which means that the number of prime numbers is infinite.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Mutually prime numbers we will name those numbers that do not have a single common divisor except 1 .

Finally, under the result of the operation i mod j we will calculate the remainder of an integer division i on j. To use the RSA algorithm, you must first generate a public and private key by completing the following steps.

1. Choose two very large prime numbers R And q.

2. Let's define n as a result of multiplication R on q (n=p·q).

3. Let's choose a large random number, which we'll call d. This number must be coprime to the result of multiplication (p – 1) · (q – 1).

4. Let's define such a number e, for which the following relation is true (e d) mod ((p – 1) (q – 1)) = 1.

5. Let's call the public key numbers e And n, and the secret key is numbers d And n.

Now, to encrypt data using a known key ( e, n), you need to do the following:

– split the encrypted text into blocks, each of which can be represented as a number M(i);

– encrypt text considered as a sequence of numbers M(i) according to the formula С(i) = (M(i) e) mod n. To decrypt this data using the secret key (d, n), you need to perform the following calculations: M(i)=(C(i) d) mod n. The result will be a lot of numbers M(i), which represent the source text.

Algorithm RSA is based on one of Euler's proven theorems, a special case of which states that if a number n representable as two prime numbers p And q, then for any x there is equality

x (p-1)(q-1) mod n = 1.

To decrypt RSA messages we will use this formula. To do this, we raise both of its parts to a power (- y):

(x (- y)(p-1)(q-1)) mod n= 1 (- y) = 1.

Now let's multiply both sides by x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Let us now remember how the public and private keys were created. We picked d such that

e d+(p-1)(q-1) y = 1,

e·d = (-y)(p-1)(q-1)+1.

Therefore, in the last expression of the previous paragraph we can replace the exponent with a number (e·d). We get (x e d) mod n = x. To read the message c i = ((m i) e)mod n it is enough to raise it to a power d modulo m:

((c i) d)mod n = ((m i) e · d) mod n = m i .

Here's a simple example of using the RSA method to encrypt a "CAB" message. For simplicity, we will use very small numbers (in practice, large numbers are used).

1. Let's choose p= 3i q= 11.

2. Let's define n= 3· 11=33.

3. Let's find (p–1) (q–1)= 20. As d choose any number that is coprime to 20, for example d= 3.

4. Choose a number e. Any number for which the relation is satisfied can be taken as such a number (e· 3)mod 20 = 1,
for example 7.

5. Imagine the encrypted message as a sequence of integers in the range 0...32. Let the letter A represented by the number 1, letter IN– the number 2, and the letter WITH– the number 3. Then the message can be represented as a sequence of numbers 312. Let’s encrypt the message using the key (7, 33):

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

C(Z) = (2 7) mod 33 = 128 mod 33 = 29.

6. Let's try to decrypt the message (9, 1, 29), obtained as a result of encryption using a known key, based on the secret key (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

M(2) = (1 3) mod 33 = 1 mod 33 = 1,

M(Z) = (29 3) mod 33 = 24389 mod 33 = 2.

Thus, as a result of decrypting the message, the original message “CAB” was received.

The cryptographic strength of the RSA algorithm is based on the assumption that it is extremely difficult to determine the secret key from a known public key, since this requires solving the problem of the existence of integer divisors. This problem does not currently allow an effective (polynomial) solution. In this regard, for keys consisting of 200 binary digits (and these are the numbers that are recommended to be used), traditional methods for finding divisors require performing a huge number of operations (about 10 23).

The RSA cryptosystem is used across a wide variety of platforms and industries. It is built into many commercial products, the number of which is constantly growing. It is used by Microsoft, Apple, Sun and Novell operating systems. In hardware, the RSA algorithm is used in secure phones, on Ethernet network cards, on smart cards, and is widely used in cryptographic equipment from Zaxus (Rasal). In addition, the algorithm is included in all major protocols for secure Internet communications, including S/MIME, SSL and S/WAN, and is also used in many institutions, such as government agencies, most corporations, government laboratories and universities .

RSA BSAFE encryption technology is used by more than 500 million users worldwide. Since the RSA algorithm is used in most cases, it can be considered the most common public key cryptosystem in the world, and this number has a clear tendency to increase as Internet users grow.

At each encryption cycle, the RSA cryptosystem transforms a binary block of plaintext m of length size(n), considered as an integer, in accordance with the formula: c = m e (mod n).

In this case n = pq , where p and q are large-width random prime numbers that are destroyed after the module and keys are formed. The public key consists of a pair of numbers e and n . Subkey e is selected as a sufficiently large number from the range 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Further, solving the equation xe + yφ(n) = 1 in integers x, y, we assume d = x, i.e. ed = 1(j(n)). In this case, for all m the following relation holds: m ed = m(n) , therefore, knowledge of d allows one to decipher cryptograms.

To ensure reliable information security, public key systems have the following two requirements.

1. Transformation of the source text must exclude its restoration based on the public key.

2. Determining a private key based on a public key must also be computationally infeasible. In this case, an exact lower bound for the complexity (number of operations) of breaking the cipher is desirable.

Public key encryption algorithms are widely used in modern information systems.

Let's look at the construction of the RSA cryptosystem using a simple example.

1. Choose p = 3 and q = 11.

2. Define n = 3 ∙ 11 = 33.

3. Find j(n) = (p – 1)(q – 1) = 20.

5. Choose a number d that satisfies 7d = 1(mod 20).

It is easy to see that d = 3(mod 20).

Let's imagine the encrypted message as a sequence of integers using the correspondence: A = 1, B = 2, C = 3, ..., Z = 26. Since size(n) = 6 , then our cryptosystem is able to encrypt letters of the Latin alphabet, considered as blocks. Let us publish the public key (e, n) = (7, 33) and invite other participants in the secret communication system to encrypt messages sent to us using it. Let such a message be CAB , which in our chosen encoding takes the form (3, 1, 2). The sender must encrypt each block and send the encrypted message to our address:

RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).

Having received the encrypted message (9, 1, 29), we can decrypt it based on the secret key (d, n) = (3, 33), raising each block to the power d = 3:

9 3 = 729 = 3(mod 33);
1 3 = 1(mod 33);
29 3 = 24389 = 2(mod 33).

For our example, it is easy to find the secret key by brute force. In practice this is impossible, because For practical use, the following values ​​of size(n) are currently recommended: :

· 512–768 bits - for individuals;

· 1024 bits - for commercial information;

· 2048 bit - for classified information.

An example of the implementation of the RSA algorithm is presented in Listings 18.1 and 18.2 (compilers - Delphi, FreePascal).

Listing 18.1. An example of the implementation of the RSA algorithm in Pascal language

program Rsa;
($APPTYPE CONSOLE)
($IFDEF FPC)
($MODE DELPHI)
($ENDIF)

uses SysUtils, uBigNumber;

//Random number generator

var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn("Enter some text to initialize the generator
random numbers (up to 256 characters):");
ReadLn(s);
i:= 1;
while(i<=255) and (i<=Length(s)) do

RSA uses two types of keys - e and d, where e is public and d is secret. Let's assume that P is the plaintext and C is the ciphertext. Alice uses C = P e mod n to create the ciphertext C from the plaintext P ; Bob uses P = C d mod n to retrieve the source text (file) sent by Alice. A very large number of n modules are created using a key generation process, which we will discuss later.

For encryption and decryption, exponentiation is used modulo. As we discussed in Lectures 12-13, when using a fast algorithm, modulo exponentiation is feasible in polynomial time. However, finding the modular logarithm is as difficult as decomposing a number modulo. There is no polynomial time algorithm for it. This means that Alice can encrypt a message with the public key (e) in polynomial time. Bob can also decrypt it in polynomial time (because he knows d). But Eve cannot decipher this message because she would have to calculate the e-root of C using modular arithmetic. Figure 14.5 shows the idea of ​​RSA.

Rice. 14.5.

In other words, Alice uses one way function(exponentiation modulo) with a loophole known only to Bob. Eve doesn't know the loophole, so she can't decipher the message. If they ever find a polynomial algorithm for the modulus of calculating the e-th root of n, then exponentiation modulo n will no longer be a one-way function.

Procedure

Figure 14.6 shows the general idea of ​​the procedure used in RSA.

RSA uses modulo exponentiation for encryption/decryption. In order to attack the private text, Eve must calculate

Rice. 14.6.

Two algebraic structures

RSA uses two algebraic structures: ring and group.

Encryption/Decryption Rings. Encryption and decryption are done using a commutative ring with two arithmetic operations: addition and multiplication. In RSA, this ring is public because module n is public. Anyone can send a message to Bob using this encryption ring.

Key Generation Groups. RSA uses the multiplicative group to generate keys. The group only supports multiplication and division (multiplicative inversion), which are necessary to create public and private keys. This group must be hidden because its module is secret. We will see that if Eve finds this module, she can easily attack the cryptographic system.

RSA uses two algebraic structures: the open ring R =< Z n , +, x > and secret group G =< Z (n)* , x >.

Key generation

Bob uses the steps shown in Algorithm 14.2 to create his public and private keys. After generating the keys, Bob declares the tuple (e, n) as his public access key: Bob stores d as his private key. Bob can give up p, q and ; they cannot change its secret key without changing the module. For security, the recommended size for each prime p or q is 512 bits (almost 154 decimal digits). This defines the module size, n 1024 bits (309 digits).

14.2. RSA key generation

In RSA, the tuple (e, n) is the public access key; integer d - secret key.

Encryption

Anyone can send a message to Bob using his public access key. Encryption in RSA can be done using an algorithm with polynomial time complexity, as shown in Algorithm 14.3. A fast algorithm for exponentiation was discussed in lectures 12-13. The size of the source text must be less than n ; if the size of the source text is larger, then it must be divided into blocks.