Sistemul De Acces Conditionat!

PKCS#1 Schemes


Algorithm: Encryption using PKCS#1v1.5 INPUT: Recipient's RSA public key, (n, e) of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11.
OUTPUT: Encrypted data block of length k bytes

1. Form the k-byte encoded message block, EB, EB = 00 || 02 || PS || 00 || D
   where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e. at least eight random bytes).
2. Convert the byte string, EB, to an integer, m, most significant byte first, m = StringToInteger(EB, k)
3. Encrypt with the RSA algorithm c = m^e mod n
4. Convert the resulting ciphertext, c, to a k-byte output block, OB OB = IntegerToString(m, k)
5. Output OB.

The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer.
Worked Example

Bob's 1024-bit RSA encryption key in hex format:
n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=010001
d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
A randomly-generated one-off session key for AES-128 might be D=4E636AF98E40F3ADCFCCB698F4E80B9F
The encoded message block, EB, after encoding but before encryption, with random padding bytes shown in green, 0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009
E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038
B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF
4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F
After RSA encryption, the output is 3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Note that the output for encryption will be different each time (or should be!) because of the random padding used.
Encrypting a message

For a plaintext message, say, PT="Hello world!"
that is, the 12 bytes in hex format, PT=48656C6C6F20776F726C6421
Then, using the 128-bit session key from above, KY=4E636AF98E40F3ADCFCCB698F4E80B9F
and the uniquely-generated 128-bit initialization vector (IV) IV=5732164B3ABB6C4969ABA381C1CA75BA
the ciphertext using AES-128 in CBC mode with PKCS padding is, CT=67290EF00818827C777929A56BC3305B
The sender would then send a transmission to the recipient (in this case, Bob) including the following information in some agreed format:



Recipient: Bob
Key Encryption Algorithm: rsaEncryption
Encrypted Key:
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Content Encryption Algorithm: aes128-cbc
IV: 5732164B3ABB6C4969ABA381C1CA75BA
Encrypted Content:
67290EF00818827C777929A56BC3305B

The usual formats used for such a message are either a CMS enveloped-data object or XML, but the above summary includes all the necessary info (well, perhaps "Bob" might be defined a bit more accurately). CMS enveloped-data objects (yes, that's enveloped not encrypted) use ASN.1 and are encoded using either DER- or BER-encoding. Cryptographic Message Syntax (CMS) is a less-ambiguous version of the earlier PKCS#7 standard (also of the same name) and is designed to be used in S/MIME messages. The terminology for CMS and ASN.1 may sound messy, but the end results are well-defined and universally-accepted. On the other hand, the XML cryptographic standards are, to be honest, a complete mess. Pretty Good Privacy (PGP) also has a format for RSA messages, although PGP stopped using RSA because of patent issues back in the 1990s.
Nothing, of course, stops you and your recipient from agreeing on your own format and using that. But be careful, even the experts get these things wrong and accidentally give away more than they realise.
Signing using PKCS#1v1.5

Algorithm: Signing using PKCS#1v1.5 INPUT: Sender's RSA private key, (n, d) of length k = |n| bytes; message, M, to be signed; message digest algorithm, Hash.
OUTPUT: Signed data block of length k bytes

1. Compute the message digest H of the message, H = Hash(M)
2. Form the byte string, T, from the message digest, H, according to the message digest algorithm, Hash, as follows

Hash T
MD5 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
SHA-1 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H SHA-25630 31 30 0d 06 09 60 86 48 01 65 03 04 02 0105 00 04 20 || H
SHA-384 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H SHA-51230 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
where T is an ASN.1 value of type DigestInfo encoded using the Distinguished Encoding Rules (DER).

1. Form the k-byte encoded message block, EB, EB = 00 || 01 || PS || 00 || T
   where || denotes concatenation and PS is a string of bytes all of value 0xFF of such length so that |EB|=k.
2. Convert the byte string, EB, to an integer m, most significant byte first, m = StringToInteger(EB, k)
3. Sign with the RSA algorithm s = m^d mod n
4. Convert the resulting signature value, s, to a k-byte output block, OB OB = IntegerToString(s, k)
5. Output OB.

Worked Example

Alice's 1024-bit RSA signing key in hex format:
n=
E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D
12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CF
C6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6
F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F
e=010001
d=
00A403C327477634346CA686B57949014B2E8AD2C862B2C7D748096A8B91F736
F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282D
F439906F34D86E085BD5656AD841F313D72D395EFE33CBFF29E4030B3D05A28F
B7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21
The message to be signed is, of course, M="abc"
that is, the 3 bytes in hex format, PT=616263
The message digest algorithm is SHA-1, so H = Hash("abc") = A9993E364706816ABA3E25717850C26C9CD0D89D
The DigestInfo value for SHA-1 is T=
3021300906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9C
D0D89D
The encoded message block, EB, after encoding but before signing is 0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00302130
0906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9CD0D89D
After RSA signing, the output is 60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F
Weaknesses in RSA

Small encryption exponent If you use a small exponent like e=3 and send the same message to different recipients and just use the RSA algorithm without adding random padding to the message, then an eavedropper could recover the plaintext. Using the same key for encryption and signingGiven that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted message using the same key then she gets the original. Acting as an oracleThere are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. So don't do that. Solutions

1. Don't use the same RSA key for encryption and signing.
2. If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
3. Always format your input before encrypting or signing.
4. Always add fresh random padding - at least 8 bytes - to your message before encrypting.
5. When decrypting, check the format of the decrypted block. If it is not as expected, return an error, not the decrypted string.
6. Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid Signature".

More Advanced Schemes

The underlying RSA computations
c = me mod n, m' = cd mod n; s = md mod n, m' = se mod n
are always the same, but there are many variants of how these can be used inside an encryption or digital signature scheme. Here are some of them.
RSAES-OAEP

The OAEP encoding technique for encryption is described in PKCS#1 version 2 and in IEEE P136. It is more secure than the PKCS#1v1.5 encoding method described above, perhaps provably secure. The encoding technique involves a mask generation function (MGF) based on a hash function and there is no obvious structure in the encoded block, unlike the PKCS#1v1.5 encoding method. Despite being the recommended method for the last decade, it is not used in practice as much as you'd expect. RSASSA-PSS

The PSS encoding method is used to encode before creating a signature. The technique is described in PKCS#1v2.1 and is similar in design to the OAEP encoding used for encryption involving an MGF based on a hash function. However, there are active patents associated with this method, so sensible implementators avoid it like the plague. There are also currently no known weaknesses with the PKCS#1v1.5 signature scheme.

X9.31 Signature Scheme


It requires using strong primes derived in a way to avoid particular attacks that are probably no longer relevant. X9.31 uses a method of encoding the message digest specific to the hash algorithm. It expects a key with length an exact multiple of 256 bits.he scheme allows for the public exponent to be an even value, but we do not consider that case here; all our values of e are assumed to be odd. The message digest hash, H, is encapsulated to form a byte string as follows EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
where PS is a string of bytes all of value 0xBB of length such that |EB|=|n|, and 0x33 is the ISO/IEC 10118 part number for SHA-1. The byte string, EB, is converted to an integer value, the message representative, f. Algorithm: Forming an X9.31/RSA2 signature value from the message representative (for odd e). INPUT: Signer's RSA private key, (n, d); integer, f, where 0 <= f < n and f ≡ 12 (mod 16).
OUTPUT: Signature, an integer s, 0 <= s < n/2, i.e. a value at least one bit shorter than n.

1. t = fd mod n
2. s = min{t, n-t}
3. Output s.

The integer, s, is converted to a byte string of length |n| bytes. Algorithm: Extracting the message representative from an X9.31/RSA2 signature value (for odd e). INPUT: Signer's RSA public key, (n, e); signature, s.
OUTPUT: Message representative, f, such that t ≡ 12 (mod 16), or "invalid signature".

1. If s is not in [0,(n-1)/2], output "invalid signature" and stop.
2. Compute t = se mod n
3. If t ≡ 12 (mod 16) then let f = t.
4. Else let f = n-t. If NOT f ≡ 12 (mod 16), output "invalid signature" and stop.
5. Output f.

The integer f is converted to a byte string of length |n| bytes and then parsed to confirm that all bytes match the required format EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
If not, output "invalid signature" and stop; otherwise output the extracted message digest hash, H. ISO/IEC 9796

IOS/IEC 9796 is an old standard devised before there was a recognised message digest function like MD5 or SHA-1. It allows the entire message to be recovered. Unfortunately, it is considered broken for signing plain text messages, but is still OK for signing message digest values.
The encapsulation mechanism weaves the input bytes into a format exactly one bit shorter than the RSA key. The signing mechanism is similar to that in ANSI X9.31 described above, but the message representative, f, is required to be f ≡ 6 (mod 16), instead of modulo 12. In other words, make sure the last 4 bits are equal to 0x6 instead of 0xC.
RSA-KEM

The RSA-KEM Key Transport Algorithm encrypts a random integer with the recipient's public key, and then uses a symmetric key-wrapping scheme to encrypt the keying data. KEM stands for Key Encapsulation Mechanism. The general algorithm is as follows

1. Generate a random integer z between 0 and n-1.
2. Encrypt the integer z with the recipient's RSA public key: c = ze mod n.
3. Derive a key-encrypting key KEK from the integer z.
4. Wrap the keying data using KEK to obtain wrapped keying data WK.
5. Output c and WK as the encrypted keying data.

This method has a higher security assurance than PKCS#1v1.5 because the input to the underlying RSA operation is random and independent of the message, and the key-encrypting key KEK is derived from it in a strong way.

Algorithm: Ferguson-Schneier Encrypt Random Key with RSA. INPUT: Recipient's RSA public key, (n, e).
OUTPUT: Content encryption key, CEK; RSA-encrypted CEK, c.

1. Compute the exact bit length of the RSA key, k = ceiling(log2(n+1)).
2. Choose a random r in the interval [0, 2k-1].
3. Compute the content encryption key by hashing r, CEK=Hash(r).
4. c = re mod n.
5. Output CEK and c.

For a plaintext message, m, the transmission sent to the recipient is IntegerToString(c) || ECEK(m), where ECEK(m) is the result of encrypting m with a symmetrical encryption algorithm using key, CEK. Given that the recipient knows the size of the RSA key and hence the exact number of bytes needed to encode c, it is a simple matter to parse the input received from the sender.

Notation and Conventions

We use the following notation and conventions in this page.

• A || B denotes concatenation of byte (or bit) strings A and B.
• |B| denotes the length of the byte (or bit) string B in bytes.
• |n| denotes the length of the non-negative integer n in bytes, |n| = ceiling(log256(n+1)).
• IntegerToString(i, n) is an n-byte encoding of the integer i with the most significant byte first (i.e. in "big-endian" order). So, for example, IntegerToString(1, 4)=00000001,
  IntegerToString(7658, 3)=001DEA
• StringToInteger(S, n) is the integer represented by the byte string S of length n bytes with the most significant byte first.
• ceiling(x) is the smallest integer, n, such that n ≥ x.

to be continued...

PKE: The RSA Algorithm

The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman (RSA) is currently one of the favorite public key encryption methods. Here is the algorithm:

1. Choose two (in practice, large 100 digit) prime numbers p and q and let n = pq.
2. Let Pi be the block of (plain) text to be encrypted. Actually Pi is the numerical equivalent of the text which may either be single letters or blocks of letters, just as long as [Only registered and activated users can see links. Click Here To Register...].
3. Choose a random value E (usually small) such that E is relatively prime to [Only registered and activated users can see links. Click Here To Register...]. Then the encrypted text is calculated from [Only registered and activated users can see links. Click Here To Register...]
   The pair of values (n,E) act as the public key.
4. To decode the ciphertext, we need to find an exponent D, which is known only to the person decoding the message, such that [Only registered and activated users can see links. Click Here To Register...]
   Note that [Only registered and activated users can see links. Click Here To Register...]. Then we may calculate
   [Only registered and activated users can see links. Click Here To Register...]
   This step is based on the following result:
   [Only registered and activated users can see links. Click Here To Register...]
   where [Only registered and activated users can see links. Click Here To Register...] Show that this result is true.

By Euler's theorem
[Only registered and activated users can see links. Click Here To Register...]
provided E and [Only registered and activated users can see links. Click Here To Register...] are relatively prime, which is true by the choice of E. So we obtain
[Only registered and activated users can see links. Click Here To Register...]

[Only registered and activated users can see links. Click Here To Register...]

[Only registered and activated users can see links. Click Here To Register...]

Therefore, we have an equation that can be used to find the "key" exponent D. The central result of the RSA algorithm is that this equation is computationally solvable in polynomial time (actually using the Euclidean Algorithm) whereas solving by factoring n requires exponential computational time.

P.S.Since [Only registered and activated users can see links. Click Here To Register...], then [Only registered and activated users can see links. Click Here To Register...] for some integer m. Thus, applying Euler's theorem we have [Only registered and activated users can see links. Click Here To Register...]




I think I'm not making ya' troubleunderstood... :D