Sistemul De Acces Conditionat!

[gessle]

-despre RSA algorithm si incepem cu inceputul:

Key Generation Algorithm


Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits

1. Compute n = pq and (φ) phi = (p-1)(q-1).
2. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1

Compute the secret exponent d, 1 < d < phi, such that ed ≡ 1

1. The public key is (n, e) and the private key is (n, d). Keep all the values d, p, q and phi secret.

• n is known as the modulus.
• e is known as the public exponent or encryption exponent or just the exponent.
• d is known as the secret exponent or decryption exponent.

Encryption


Sender A does the following:-

1. Obtains the recipient B's public key (n, e).
2. Represents the plaintext message as a positive integer m

1. Computes the ciphertext c = me mod n.
2. Sends the ciphertext c to B.

Decryption

Recipient B does the following:-

1. Uses his private key (n, d) to compute m = cd mod n.
2. Extracts the plaintext from the message representative m.

Digital signing

Sender A does the following:-

1. Creates a message digest of the information to be sent.
2. Represents this digest as an integer m between 0 and n-1.
3. Uses her private key (n, d) to compute the signature s = md mod n.
4. Sends this signature s to the recipient, B.

Signature verification

Recipient B does the following:-

1. Uses sender A's public key (n, e) to compute integer v = se mod n.
2. Extracts the message digest from this integer.
3. Independently computes the message digest of the information that has been signed.
4. If both message digests are identical, the signature is valid.

Summary of RSA

• n = pq, where p and q are distinct primes.
• phi, φ = (p-1)(q-1)
• e < n such that gcd(e, phi)=1
• d = e-1 mod phi.
• c = me mod n, 1<m<n.
• m = cd mod n.

Key length

When we talk about the key length of an RSA key, we are referring to the length of the modulus, n, in bits. The minimum recommended key length for a secure RSA transmission is currently 1024 bits. A key length of 512 bits is now no longer considered secure, although cracking it is still not a trivial task for the likes of you and me. The longer your information is needed to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.
There is small one area of confusion in defining the key length. One convention is that the key length is the position of the most significant bit in n that has value '1', where the least significant bit is at position 1. Equivalently, key length = ceiling(log2(n+1)). The other convention, sometimes used, is that the key length is the number of bytes needed to store n multiplied by eight, i.e. ceiling(log256(n+1)).



The key used in the RSA Example paper s an example. In hex form the modulus is 0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB
The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position 508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method. You can get into difficulties with the X9.31 method for signatures if you use the latter convention.
Computational Efficiency and the Chinese Remainder Theorem (CRT)

Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation a = be mod n is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as
e = e(k-1)e(k-2)...e(1)e(0)
where e(k-1) is the most significant non-zero bit and bit e(0) the least.
set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square */
if e(j) == 1 then
y = y * x mod n /* multiply */
end
return y
The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c = me mod n. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. Don't make the mistake of trying to contrive a small value for d; it is not secure.
An alternative method of representing the private key uses the Chinese Remainder Theorem (CRT). The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is four times faster overall than calculating m = cd mod n. For more details, see [PKCS1]. The extra values for the private key are:-
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q
These are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-
m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq
Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.

Someone has pointed out that most large integer packages will fail when computing h if m1 < m2. This can be easily fixed by computing h = qInv(m1 + p - m2) mod p or, alternatively, as we do it in our BigDigits implementation of RSA,
if (bdCompare(m1, m2) < 0)
bdAdd(m1, m1, p);
bdSubtract(m1, m1, m2);
/* Let h = qInv ( m_1 - m_2 ) mod p. */
bdModMult(h, qInv, m1, p);

[gessle]

A very simple example of RSA encryption

This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand).

1. Select primes p=11, q=3.
2. n = pq = 11.3 = 33
   phi = (p-1)(q-1) = 10.2 = 20
3. Choose e=3
   Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
   and check gcd(e, q-1) = gcd(3, 2) = 1
   therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that ed ≡ 1 (mod phi)
   i.e. compute d = e-1 mod phi = 3-1 mod 20
   i.e. find a value for d such that phi divides (ed-1)
   i.e. find d such that 20 divides 3d-1.
   Simple testing (d = 1, 2, ...) gives d = 7
   Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
5. Public key = (n, e) = (33, 3)
   Private key = (n, d) = (33, 7).

This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7,
c = me mod n = 73 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = cd mod n = 137 mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a = bc mod n = (b mod n).(c mod n) mod n
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
m' = 137 mod 33 = 13(3+3+1) mod 33 = 133.133.13 mod 33
= (133 mod 33).(133 mod 33).(13 mod 33) mod 33
= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33
= 19.19.13 mod 33 = 4693 mod 33
= 7.
Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get
m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4

m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32
Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any n, no matter how large. But in practice, higher values shouldn't be a problem when we use large values for n in the order of several hundred bits.
If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers m1, m2, ...
(9,6,13,13,16,24,16,19,13,5)
Using our table above, we obtain ciphertext integers c1, c2, ... (3,18,19,19,4,30,4,28,19,26)
Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption. Remember that calculating me mod n is easy, but calculating the inverse c-e mod n is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.





A slightly less simple example of the RSA algorithm

This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block. ATTACKxATxSEVEN = ATT ACK XAT XSE VEN
In the same way that a decimal number can be represented as the sum of powers of ten, e.g.
135 = 1 x 102 + 3 x 101 + 5,
we could represent our blocks of three characters in base 26 using A=0, B=1, C=2, ..., Z=25 [FONT='Courier New',Courier,monospace] ATT = 0 x 262 + 19 x 261 + 19 = 513
ACK = 0 x 262 + 2 x 261 + 10 = 62
XAT = 23 x 262 + 0 x 261 + 19 = 15567
XSE = 23 x 262 + 18 x 261 + 4 = 16020
VEN = 21 x 262 + 4 x 261 + 13 = 14313
[/FONT]
For this example, to keep things simple, we'll not worry about numbers and punctuation characters, or what happens with groups AAA or AAB.
In this system of encoding, the maximum value of a group (ZZZ) would be 263-1 = 17575, so we require a modulus n greater than this value.

1. We "generate" primes p=137 and q=131 (we cheat by looking for suitable primes around √n)
2. n = pq = 137.131 = 17947
   phi = (p-1)(q-1) = 136.130 = 17680
3. Select e = 3
   check gcd(e, p-1) = gcd(3, 136) = 1, OK and
   check gcd(e, q-1) = gcd(3, 130) = 1, OK.
4. Compute d = e-1 mod phi = 3-1 mod 17680 = 11787.
5. Hence public key, (n, e) = (17947, 3) and private key (n, d) = (17947, 11787).

Question: Why couldn't we use e=17 here?
To encrypt the first integer that represents "ATT", we have
c = me mod n = 5133 mod 17947 = 8363.
We can verify that our private key is valid by decrypting
m' = cd mod n = 836311787 mod 17947 = 513.
Overall, our plaintext is represented by the set of integers m
(513, 62, 15567, 16020, 14313)
We compute corresponding ciphertext integers c = me mod n, (which is still possible by using a calculator)
(8363, 5017, 11884, 9546, 13366)
You are welcome to compute the inverse of these ciphertext integers using m = cd mod n to verify that the RSA algorithm still holds. However, this is now outside the realms of hand calculations unless you are very patient.





A real example

In practice, we don't have a series of small integers to encrypt like we had in the above examples, we just have one big one. We put our message into an octet string, most significant byte first, and then convert to a large integer. Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES or AES-128. We then use the much slower public key encryption algorithm to encrypt just the session key.
The sender A then transmits a message to the recipient B in a format something like this:




Session key encrypted with RSA = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx



The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the private key.
If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.
When signing, it is usual to use RSA to sign the message digest of the message rather than the message itself. A one-way hash function like SHA-1 or SHA-256 is used. The sender A then sends the signed message to B in a format like this:




Hash algorithm = hh
Message content = xxxxxxxxx...xxx
Signature = digest signed with RSA = xxxx



The recipient will decrypt the signature to extract the signed message digest, m; independently compute the message digest, m', of the actual message content; and check that m and m' are equal. Putting the message digest algorithm at the beginning of the message enables the recipient to compute the message digest on the fly while reading the message.