Brno University of Technology
Faculty of Telecommunications
Project:
“Protection of the information in
telecommunications”
Maded by:
Students of ISTU, gr.7-28-1
Korostin A. A.
Kulyabin E. N.
Checked by:
Ing. Vladislav Škorpil, CSc.
Brno, 2002.
Contents:
1. Theoretical part.
1.1. Substantiation of a choice of the given theme…………………3 p.
1.2. Search of the decision………………………………………….3 p.
1.3. Realization of algorithm………………………………………..4 p.
1.4. Its “pluss” and “minuses”………………………………………4 p.
1.5. Description of RSA……………………………………………..5 p.
2. Practical part.
2.1. Sources of program for encrypting………………………………10 p.
Conclusion...... 21 p.
1. Theoretical part.
1.1. Substantiation of a choice of the given theme.
Now all over the world the wide circulation was received with telecommunications. By means of them there is a communication as between usual users, and between confidential objects. Frequently the usual user at all does not suspect, that such the information and what its price. But the information are all. And in many cases it is required, that it has remained not read people to which it is not intended. With development of mankind volumes of the transmitted information, including what demands the certain privacy have increased. Programmers and mathematics try to solve a problem in creation of such algorithm which had two major qualities:
1. Reliability.
2. Speed.
And we have decided to bring our maybe not big contribution to this business.
1.2. Search of the decision.
For writing a program which could quickly and reliably to cipher the text, first of all it was required to find and read the information on already existing algorithms (one them them are described in a theoretical part). The majority of known algorithms use algorithm of imposing of an electronic key on the text which is necessary for enciphering. Stability breaking such algorithms is defined only by length of a key and speed of a computer on which break open this code. Breaking is impossible in one case - if the length of a key is equal to length of the text. We have decided to go on this way. At enciphering a wide circulation have received hash functions. In our program from the entered password the number in length in 16 bytes with the help of hash-function MD5 is generated. Advantage of the given method of introduction of the password is that:
1. The password is not checked anywhere and not stored, that excludes any opportunity to find out the password (if, certainly, the person of him will not tell it).
2. 2. At introduction of the incorrect password even if it differs on one symbol, the target number will be absolute another.
After generation 16-byte number A from an initial file (which is required to be ciphered), 1 byte undertakes and with the help of operation XOR is imposed on the first (the first byte) A. For increase of speed of the given algorithm function of reception of random numbers is used. As is known, the computer uses the certain function for reception of random numbers. If on an input of this function to submit the same number the same sequences will turn out. This function is used for reception of the second which will be imposed on the second byte of the file subject to enciphering. For the third byte the second byte of number undertakes from A. And process repeats. The second password is superfluous in any sense. The program counts up number of symbols in the second password. The set forth above cycle will repeat so much time, what length of the second password. But as length of number A at us of 16 bytes the second password should contain no more than 16 symbols. It was possible to enter number, but we have chosen a word, because it can be used at the further works at improvement of algorithm. The algorithm of decoding occurs similarly. During development the algorithm has undergone significant changes. Development of algorithm from the beginning and up to the end further will be described.
Variant № 1.
The program contains a certain matrix which represents a set of images of symbols. For the image of each letter of the password the matrix 7х8 bats is used. For example, at input of password VUT, in memory of a computer the following matrix of transformations is formed:
1 / 0 / 0 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 1 / 1 / 1 / 1 / 1 / 10 / 1 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 1 / 0 / 0 / 1
0 / 1 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
0 / 1 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
0 / 0 / 1 / 0 / 1 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
0 / 0 / 1 / 0 / 1 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 0 / 1 / 1 / 1 / 0 / 1 / 0 / 0 / 0 / 1 / 0 / 0 / 0
Then she(it) will be transformed to an one-dimensional file (7*8*3)/8=21 byte. From the file it is read 21 bytes of the information and it is imposed on the received key. Then this key varies according to other password. This method "beautiful", but has a number of lacks:
1. At known images of symbols decoding of the message is possible.
2. The file contains only limited quantity of images of symbols, i.e. the password can be entered only the certain symbols (for example, the English letters).
Variant № 2.
It represents variant № 1, but differs from it filling of a matrix of transformations. Let’s allow, that in the password n various symbols then we shall create n matrixes 7х8 with the help of any function (for example, the generator of random numbers). The first, or initial, as number for this function the code of the subsequent (after given) a symbol can serve. Such matrix changes according to the second password. This variant was not realized, as there was a variant № 3.
1.3. Realization of algorithm.
The matrix of transformations in the given variant is generated as follows: from the password number A is generated (hash-function) and the first byte of this number, the subsequent of 7 bytes are produced with the help of the generator of random numbers undertakes, using the first byte of number A. This cycle repeats so much time, how many quantity of symbols in the second password. After the program uses all of 16 bytes of number A, it generates new number, having taken for initial old number A.
1.4. Its “pluss” and “minuses”.
The matrix of transformation in the given variant is generated as follows: from the password number A is generated (hash-function) and the first byte of this number, the subsequent of 7 bytes founds with the help of the generator of random numbers undertakes, using the first byte of number A. This cycle repeats so much time, how many quantity symbols in the second password. After the program uses all of 16 bytes of number A, it generates new number, having taken for initial old number A. Lack of the given method that it is possible to use a brute-force method to pick up initial number A, knowing function of generation of random numbers. If the first byte of number A it is possible to find the subsequent of 7 bytes used at decrypting is known. Having touched 256 variants, it is possible to find the necessary number on 8 symbols. In the same way it is possible to calculate and other figures of number A. Thus, the given algorithm is unstable to breaking. In the final version of the program we generate not 7 bytes but only 2, that very much complicates selection of a key. Stability of algorithm breaking has increased. Also advantage of the given algorithm is its speed: on computer AMD 1200Mhz, 256Mb RAM speed of enciphering makes 732,5 kB/sec. Speed of algorithm still can be increased if to copy it in language of the assembler. We used language DELPHI. For the lack of time we had not time to copy the given program on the assembler. The given advantage allows to realize our algorithm on the microprocessor, for example, families PIC. In case of interception of the information on a liaison channel on definition of algorithm and decoding a lot of time will be spent, the information already will have time to become outdated. Having brought all results, we realized, in our opinion, the optimal variant of algorithm of enciphering.
1.5. Description of RSA.
Soon after Merkle’s knapsack algorithm came the first full-fledged public-key algorithm, one that works for encryption and digital signatures: RSA. Of all the public-key algorithms proposed over the years, RSA is by far the easiest to understand and implement. (Martin Gardner published an early description of the algorithm in his “Mathematical Games” column in Scientific American.) It is also the most popular. Named after the three inventors—Ron Rivest, Adi Shamir, and Leonard Adleman—it has since withstood years of extensive cryptanalysis. Although the cryptanalysis neither proved nor disproved RSA’s security, it does suggest a confidence level in the algorithm.
RSA gets its security from the difficulty of factoring large numbers. The public and private keys are functions of a pair of large (100 to 200 digits or even larger) prime numbers. Recovering the plaintext from the public key and the ciphertext is conjectured to be equivalent to factoring the product of the two primes.
To generate the two keys, choose two random large prime numbers, p and q. For maximum security, choose p and q of equal length. Compute the product:
n = pq
Then randomly choose the encryption key, e, such that e and (p - 1)(q - 1) are relatively prime. Finally, use the extended Euclidean algorithm to compute the decryption key, d, such that
ed ≡ 1 mod (p - 1)(q - 1)
In other words,
d = e-1 mod ((p - 1)(q - 1))
Note that d and n are also relatively prime. The numbers e and n are the public key; the number d is the private key. The two primes, p and q, are no longer needed. They should be discarded, but never revealed.
To encrypt a message m, first divide it into numerical blocks smaller than n (with binary data, choose the largest power of 2 less than n). That is, if both p and q are 100-digit primes, then n will have just under 200 digits and each message block, mi , should be just under 200 digits long. (If you need to encrypt a fixed number of blocks, you can pad them with a few zeros on the left to ensure that they will always be less than n.) The encrypted message, c, will be made up of similarly sized message blocks, ci, of about the same length. The encryption formula is simply
ci = mie mod n
To decrypt a message, take each encrypted block ci and compute
mi = cid mod n
Since
cid = (mie)d = mied = mik(p - 1)(q- 1)+ 1 = mi mik(p- 1)(q- 1) = mi*1 = mi; all (mod n)
the formula recovers the message. This is summarized in Table 19.2.
The message could just as easily have been encrypted with d and decrypted with e; the choice is arbitrary. I will spare you the number theory that proves why this works; most current texts on cryptography cover it in detail.
A short example will probably go a long way to making this clearer. If p = 47 and q = 71, then
n = pq = 3337
The encryption key, e, must have no factors in common with
(p - 1)(q - 1) = 46 * 70 = 3220
Choose e (at random) to be 79. In that case
d = 79-1 mod 3220 = 1019
This number was calculated using the extended Euclidean algorithm. Publish e and n, and keep d secret. Discard p and q.
To encrypt the message
m = 6882326879666683
first break it into small blocks. Three-digit blocks work nicely in this case. The message is split into six blocks, mi, in which
m1 = 688
m2 = 232
m3 = 687
m4 = 966
m5 = 668
m6 = 003
The first block is encrypted as
68879 mod 3337 = 1570 = c1
Performing the same operation on the subsequent blocks generates an encrypted message:
c = 1570 2756 2091 2276 2423 158
Decrypting the message requires performing the same exponentiation using the decryption key of 1019, so
15701019 mod 3337 = 688 = m1
The rest of the message can be recovered in this manner.
RSA EncryptionPublic Key:
n / product of two primes, p and q (p and q must remain secret)
e / relatively prime to (p - 1)(q - 1)
Private Key:
d / e-1 mod ((p - 1)(q - 1))
Encrypting:
c = me mod n
Decrypting:
m = cd mod n
Speed of RSA
In hardware, RSA is about 1000 times slower than DES. The fastest VLSI hardware implementation for RSA with a 512-bit modulus has a throughput of 64 kilobits per second. There are also chips that perform 1024-bit RSA encryption. Currently chips are being planned that will approach 1 megabit per second using a 512-bit modulus; they will probably be available in 1995. Manufacturers have also implemented RSA in smart cards; these implementations are slower.
In software, DES is about 100 times faster than RSA. These numbers may change slightly as technology changes, but RSA will never approach the speed of symmetric algorithms.
Security of RSA
The security of RSA depends wholly on the problem of factoring large numbers. Technically, that’s a lie. It is conjectured that the security of RSA depends on the problem of factoring large numbers. It has never been mathematically proven that you need to factor n to calculate m from c and e. It is conceivable that an entirely different way to cryptanalyze RSA might be discovered. However, if this new way allows the cryptanalyst to deduce d, it could also be used as a new way to factor large numbers. I wouldn’t worry about it too much.