Newsgroup: it.comp.sicurezza.unix
Titolo: RSA Public-key Encription

Scusate se in inglese, ma penso ne valga la pena dargli una letta.
ciap
p
----- snip -----
RSA Public-key Encryption
-----------------------------
The RSA cryptosystem, named after its inventor Ron Rivest, Adi Shamir 
and Leonard Adleman, is the most widely used public-key cryptosystem. It 
was created in 1977.
In this article I can't explain how to crack a RSA security, but I will 
explain some of the attacks you shouldn't try...
First things first... Let's try to understand the algorithm...
The user takes 2 large primes, p and q, and computes their product 
(n=pq). n is called the modulus. The user then chooses a number, e (1 < 
e > n). Then another number, d, is found. According to this algorithm: 
(ed-1)/(p-1)(q-1)
e is called the public exponent
d is called the private exponent
Small example:
----------------
Let say: p =5 and q = 11
so n = 55
The least common multiple of (p-1)(q-1) is 20 = 2² x 5
Therefore in this case, any key , e, not divisible by 2 or 5 will have a 
matching key, d(e
must be relativly prime to (p-1)(q-1) for it to be the key).
Let e = 7
(ed-1) mod (p-1)(q-1) = 0 ==> d = 3
(for those who don't know mod means read any program language book)
Let the plaintext message, m = b = 2
The ciphertext, c = me mod n = 2^7 mod 55 = 18
To decrypt this information it is necessary to know d.
m’ = c^d mod n = 18³ mod 55 = 2 ==> The message is successfully encrypted
In real life this is much more difficult. RSA doesn’t use small 
integers, but 6 – 8 digit primes. So doing it by hand is nearly impossible…
In 1997, a specific assessment of the security of 512-bit RSA keys shows 
that one may be factored for less than $1,000,000 in cost and eight 
months of effort. It is therefore believed that 512-bit keys provide 
insufficient security for anything other than short-term needs. RSA 
Laboratories currently recommends key sizes of 768 bits for personal 
use, 1024 bits for corporate use, and 2048 bits for extremely valuable 
keys like the root-key pair used by a certifying authority. Security can 
be increased by changing a users key regularly and it is typical for a 
user’s key to expire after 2 years.
“Real World” Usage Of The RSA Algorithm
----------------------------------------------------------
DES, and other block ciphers, are much faster in operation than RSA. 
Typically, in software, DES is 100 times faster than RSA and in hardware 
can be between 1000 and 10000 times faster depending on the 
implementation. Because of the length of time taken for public key 
encryption a public key system such as RSA is often used in conjunction 
with a secret-key system such as DES. In this case the message is 
encrypted with a randomly chosen DES key and the key itself is encrypted 
and sent with RSA. This method combines the low number of keys required 
for RSA with the high-speed operation of DES.
Attack Preventing
----------------------------
RSA prevented the security from well known attacks…
1) Relation of Factoring
2) Small Encryption exponent e
3) Forward Search Attack
4) Small decryption exponent d
5) Multiplicative properties
6) Common Modulus attack
7) Cycling Attacks
8) Message Concealing
I took this completely from the book: Handbool of Applied Cryptography 
(can be found on the net completely)
(i) Relation to factoring
The task faced by a passive adversary is that of recovering 
plaintextmfrom the corresponding ciphertext c, given the public 
information (n; e) of the intended receiver A. This is called the RSA 
problem (RSAP), which was introduced in x3.3. There is no efficient 
algorithm known for this problem. One possible approach which an 
adversary could employ to solving the RSA problem is to first factor n, 
and then compute _ and d just as A did in Algorithm 8.1. Once d is 
obtained, the adversary can decrypt any ciphertext intended for A. On 
the other hand, if an adversary could somehow compute d, then it could 
subsequently
factor n efficiently as follows. First note that since ed _ 1 (mod _), 
there is an integer k such that ed - 1 = k_. Hence, by Fact 2.126(i), 
aed-1 _ 1 (mod n) for all
a 2 Z_
n. Let ed - 1 = t, where t is an odd integer. Then it can be shown that 
there exists an i 2 [1; s] such that a2i-1t 6_ _1 (mod n) and a2it _ 1 
(mod n) for at least half of all a 2 Z_
n; if a and i are such integers then gcd(a2i-1t - 1; n) is a non-trivial 
factor of n. Thus the adversary simply needs to repeatedly select random 
a 2 Z_n and check if an i 2 [1; s] satisfying the above property exists; 
the expected number of trials before a non-trivial factor of n is 
obtained is 2. This discussion establishes the following.
8.6 Fact The problemof computing the RSAdecryption exponent d from the 
public key (n; e), and the problem of factoring n, are computationally 
equivalent. Handbook of Applied Cryptography by A. Menezes, P. van 
Oorschot and S. Vanstone. 288 Ch. 8 Public-Key Encryption When 
generating RSA keys, it is imperative that the primes p and q be 
selected in such a way that factoring n = pq is computationally 
infeasible; see Note 8.8 for more details.
(ii) Small encryption exponent e
In order to improve the efficiency of encryption, it is desirable to 
select a small encryption
exponent e (see Note 8.9) such as e = 3. A group of entities may all 
have the same encryption exponent e, however, each entity in the group 
must have its own distinct modulus (cf. x8.2.2(vi)). If an entity A 
wishes to send the same message m to three entities whose public moduli 
are n1, n2, n3, and whose encryption exponents are e = 3, then A would send
ci = m3 mod ni, for i = 1; 2; 3. Since these moduli are most likely 
pairwise relatively prime, an eavesdropper observing c1, c2, c3 can use 
Gauss’s algorithm (Algorithm 2.121)
to find a solution x, 0 _ x < n1n2n3, to the three congruences
8<:
x _ c1 (mod n1)
x _ c2 (mod n2)
x _ c3 (mod n3):
Since m3 < n1n2n3, by the Chinese remainder theorem (Fact 2.120), it 
must be the case that x = m3. Hence, by computing the integer cube root 
of x, the eavesdropper can recover
the plaintext m. Thus a small encryption exponent such as e = 3 should 
not be used if the same message, or even the same message with known 
variations, is sent to many entities. Alternatively,
to prevent against such an attack, a pseudorandomly generated bitstring 
of appropriate length (taking into account Coppersmith’s attacks 
mentioned on pages 313–314)
should be appended to the plaintext message prior to encryption; the 
pseudorandom bitstring should be independently generated for each 
encryption. This process is sometimes referred to as salting the 
message. Small encryption exponents are also a problem for small 
messages m, because ifm<
n1=e, then m can be recovered from the ciphertext c = me mod n simply by 
computing the integer eth root of c; salting plaintext messages also 
circumvents this problem.
(iii) Forward search attack
If themessage space is small or predictable, an adversary can decrypt a 
ciphertext c by simply encrypting all possible plaintext messages until 
c is obtained. Salting the message as
described above is one simple method of preventing such an attack.
(iv) Small decryption exponent d
As was the case with the encryption exponent e, it may seem desirable to 
select a small decryption exponent d in order to improve the efficiency 
of decryption.1 However, if gcd(p-
1; q - 1) is small, as is typically the case, and if d has up to 
approximately one-quarter as many bits as the modulus n, then there is 
an efficient algorithm (referenced on page 313)
for computing d from the public information (n; e). This algorithm 
cannot be extended to the case where d is approximately the same size as 
n. Hence, to avoid this attack, the decryption exponent d should be 
roughly the same size as n.
(v) Multiplicative properties Let m1 and m2 be two plaintext messages, 
and let c1 and c2 be their respective RSA encryptions.
Observe that (m1m2)e _ me 1me 2 _ c1c2 (mod n):
1In this case, one would select d first and then compute e in Algorithm 
8.1, rather than vice-versa.
c
1997 by CRC Press, Inc.—See accompanying notice at front of chapter.
x 8.2 RSA public-key encryption 289
In other words, the ciphertext corresponding to the plaintext m = m1m2 
mod n is c =
c1c2 mod n; this is sometimes referred to as the homomorphic property of 
RSA. This observation
leads to the following adaptive chosen-ciphertext attack on RSA encryption.
Suppose that an active adversarywishes to decrypt a particular 
ciphertext c = me mod
n intended for A. Suppose also that A will decrypt arbitrary ciphertext 
for the adversary,
other than c itself. The adversary can conceal c by selecting a random 
integer x 2 Z_
n
and computing c = cxe mod n. Upon presentation of c, A will compute for 
the adversary
m = (c)d mod n. Since
m _ (c)d _ cd(xe)d _ mx (mod n);
the adversary can then compute m = mx-1 mod n.
This adaptive chosen-ciphertext attack should be circumvented in 
practice by imposing
some structural constraints on plaintext messages. If a ciphertext c is 
decrypted to amessage
not possessing this structure, then c is rejected by the decryptor as 
being fraudulent. Now,
if a plaintext message m has this (carefully chosen) structure, then 
with high probability
mx mod n will not for x 2 Z_
n. Thus the adaptive chosen-ciphertext attack described in
the previous paragraph will fail because A will not decrypt c for the 
adversary. Note 8.63
provides a powerful technique for guarding against adaptive 
chosen-ciphertext and other
kinds of attacks.
(vi) Common modulus attack
The following discussion demonstrates why it is imperative for each 
entity to choose its own RSA modulus n.
It is sometimes suggested that a central trusted authority should select 
a single RSA modulus n, and then distribute a distinct 
encryption/decryption exponent pair (ei; di) to each entity in a 
network. However, as shown in (i) above, knowledge of any (ei; di) pair 
allows for the factorization of the modulus n, and hence any entity 
could subsequently determine the decryption exponents of all other 
entities in the network. Also, if a singlemessage were encrypted and 
sent to two or more entities in the network, then there is a technique 
by which an eavesdropper (any entity not in the network) could recover 
the message with high probability using only publicly available information.
(vii) Cycling attacks
Let c = me mod n be a ciphertext. Let k be a positive integer such that cek
_ c (mod n);
since encryption is a permutation on the message space f0; 1; : : : ; n 
- 1g such an integer k must exist. For the same reason it must be the 
case that cek-1_ m (mod n). This observation leads to the following 
cycling attack on RSA encryption. An adversary computes
ce mod n, ce2
mod n, ce3
mod n; : : : until c is obtained for the first time. If cek
mod n =
c, then the previous number in the cycle, namely cek-1
mod n, is equal to the plaintext m.
A generalized cycling attack is to find the smallest positive integer u 
such that f =
gcd(ceu
- c; n) > 1. If
ceu
_ c (mod p) and ceu
6_ c (mod q) (8.1)
then f = p. Similarly, if
ceu
6_ c (mod p) and ceu
_ c (mod q) (8.2)
then f = q. In either case, n has been factored, and the adversary can 
recover d and then m. On the other hand, if both
ceu
_ c (mod p) and ceu
_ c (mod q); (8.3)
Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. 
Vanstone.
290 Ch. 8 Public-Key Encryption
then f = n and ceu
_ c (mod n). In fact, u must be the smallest positive integer k
for which cek
_ c (mod n). In this case, the basic cycling attack has succeeded and so
m = ceu-1
mod n can be computed efficiently. Since (8.3) is expected to occur much 
less
frequently than (8.1) or (8.2), the generalized cycling attack usually 
terminates before the
cycling attack does. For this reason, the generalized cycling attack can 
be viewed as being
essentially an algorithm for factoring n.
Since factoring n is assumed to be intractable, these cycling attacks do 
not pose a threat
to the security of RSA encryption.
(viii) Message concealing
A plaintext message m, 0 _ m _ n-1, in the RSA public-key encryption 
scheme is said to be unconcealed if it encrypts to itself; that is,me _ 
m (mod n). There are always some messages which are unconcealed (for 
example m = 0, m = 1, and m = n - 1). In fact, the number of unconcealed 
messages is exactly
[1 + gcd(e - 1; p - 1)] _ [1 + gcd(e - 1; q - 1)]:
Since e-1, p-1 and q -1 are all even, the number of unconcealed messages 
is always at least 9. If p and q are random primes, and if e is chosen 
at random (or if e is chosen to be a small number such as e = 3 or e = 
216 + 1 = 65537), then the proportion of messages which are unconcealed 
by RSA encryption will, in general, be negligibly small, and hence 
unconcealed messages do not pose a threat to the security of RSA 
encryption in practice.
----- snip -----

 Scusate se in inglese, ma penso ne valga la pena dargli una letta.
Sicuramente interessante... ma non era il caso di postare
semplicemente il link ?
http://neworder.box.sk/newsread_print.php?newsid=6611
Bye, G.

sicuramente; mi son lasciato prendere dal fatto che leggo quasi sempre 
offline, e mi piace vedere tutto e subito :)
next time non mancherò
ciap
p


 next time non mancherò
Anche io leggo sempre off-line e mi fatto piacere il testo incollato, e'
contrario a qualche regola?
Grazie

 Grazie
solitamente si legge offline perchč stando on paghi...
se tutti scrivessero msg da 14k, ci vorrebbe un sacco per scaricare tutto =
piů soldi spesi
:-)
č solo per quello che usualmente si cerca di scrivere messaggi non
stringati, ma quantomeno non esagerati. č lo stesso motivo per cui non sono
accettati gli attachments su gruppi non binari.
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (
http://www.grisoft.com
).
Version: 6.0.427 / Virus Database: 240 - Release Date: 06/12/2002

 ha scritto nel messaggio
news:3DF2874F...@softhome.net...
