Взломан алгоритм шифрования RSA
Gena Makhomed
>>> Взломан алгоритм шифрования RSA
Филиппинский математик-энтузиаст разработал новый метод декодирования
алгоритма шифрования RSA, основанный всего лишь на трех простых формулах,
сообщает филиппинская газета Manila Bulletin.
Лео де Велез (Leo de Velez) вывел три формулы позволяющие
декодировать сообщения, зашифрованные по алгоритму RSA.
RSA был разработан в 1977 году Роном Ривестом (Ron Rivest), Ади Шамиром (Adi
Shamir) и Леонардом Адельманом (Leonard Adleman) и является в настоящее время
наиболее часто применяемым механизмом защиты информации. Он включен в состав
браузеров от компаний Netscape и Microsoft, а также таких известных продуктов,
как Lotus Notes, Intuit Quicken и др.
Основой криптостойкости работы RSA является тот факт, что произведение двух
простых больших чисел невозможно разложить на множители за обозримое время.
Два больших простых числа перемножаются и их произведение считается открытым
ключом, с помощью которого можно зашифровать сообщения. Расшифровать подобное
закодированное сообщение можно только зная один из множителей ("секретный
ключ"). Более подробную информацию о работе алгоритма можно найти
на веб-сайте RSA.
CNews.ru
===-===-===
<HTML><HEAD><TITLE>MB - Pinoy who discovered new faster way
of decoding RSA encryption explains claim (2/6/01)</TITLE>
<META content="2001-02-06 05:00:00" name=PublishDate>
<BODY><a href="http://www.mb.com.ph/INFO/2001-02/IT020601.asp">
[ http://www.mb.com.ph/INFO/2001-02/IT020601.asp ]</a><br>
<div align=right>Tuesday, 6 February 2001</div>
<H2>Pinoy who discovered new faster way of decoding RSA encryption
explains claim</H2>
<p>Mathematics enthusiast Leo de Velez who claims to have
discovered a faster way of decoding RSA encryption believes that his
findings are solid since nobody is still using his formula of 2^X =
1 mod N where N is given as the public key, find X.</p>
<P>RSA is an Internet encryption and authentication system that uses
an algorithm developed in 1977 by Ron Rivest, Adi Shamir, and
Leonard Adleman.
<P>"To do this, one approach that I claim as also mine is to
multiple N with a number Y. Such that N * Y will give a binary
product with all bit one," De Velez said.
<P>Example: N = 55, its binary representation is 110111 If we
multiply N by Y = 19065, the product will be equal to
11111111111111111111 (20 digits).
<P>To find Y = 19065, we just add 110111 to itself many times but
shifting the binary number to the left so that we always add 1 to
the zero to make it 1.
<P>For instance, <PRE> 110111
+ 110111
-------
111101111
+110111
------------
10101011111
</PRE>
<P>and so on until the sum is all 1. De Velez said the shifting to
the left represents the number Y = 19065 = 100101001111001. The
first digit on the right = 1 representing the top most number in the
addition above.
<P>Then, it was shifted 3 position to the left, the first two
position, since there was no addition represents 0, the third
represent 1. You can compare it to the binary digit of Y above.
<P>Going back, the number of 1's in the final sum is 20 and that is
X. This means X = 20. This will now be used to calculate the private
keys.
<P>De Velez said that RSA has sent him an e-mail to say that the
other keys that he discovered can actually decipher 100 percent of
the codes. "This means the private key is not unique which a layman
like me believe is unique."
<P>Ron Rivest of RSA has informed De Velez: "In response to my
inquiry, which was: Maybe you could explain how it works on the
following example?
<P>n = 55 <BR>e = 3<BR>ciphertext = 2<BR>
<P>"You (De Velez) said: Using the extended Euclidian algorithm
twice with some empirical formula, you can get a private key of 7
which can decipher about 80 percent of the codes. Using again the
extended Euclidian algorithm, you can calculate 27, 47 as some of
the other private keys that can decipher the code."
<P>"You may or not be aware that any decryption exponent d that
satisfies e * d = 1 (mod lambda(n)) where lambda(n) = lcm(p-1,q-1)
will work perfectly as an RSA decryption exponent, since every
element of the multiplicative group modulo n (where n = pq) will
have order dividing lambda(n).
<P>Note that lambda(n) divides phi(n) always. In the example with n
= 55, we have phi(n) = (p-1)(q-1) = 40 and lambda(n) = 20.
<P>Since 7 is a multiplicative inverse of 3, modulo 20, then 7 is a
perfectly good decoding exponent for 3. It doesn't just decrypt 80%
of the values; it decrypts them all. Since 3*27=81=1 (mod 20) and
3*47=141=1 (mod 20), the decoding exponents 27 and 47 are also
perfect decoders corresponding to the exponent 3.
<P>Rivest noted that any technique that can find a multiplicative
inverse of e modulo lambda(n) can be used to factor n. "So if your
approach finds such exponents somehow, then you also have
a factoring algorithm, not just an algorithm to break RSA,"
Rivest said. (Edu H. Lopez)</p></BODY></HTML>
Max Alekseyev
Replying to a message of Gena Makhomed to All:
>>>> Взломан алгоритм шифрования RSA
GM> Филиппинский математик-энтузиаст разработал новый метод декодирования
GM> алгоритма шифрования RSA, основанный всего лишь на трех простых
GM> формулах, сообщает филиппинская газета Manila Bulletin.
Сабж - это гон. До чего падки журналисты на сенсации. ;-(
======================================================
* Original in area RU.CRYPT
* From: Max Alekseyev 2:5015/60 05.02.2001 23:40:11
* To : Alexander Pototsky
* Subj: мысли есть?
======================================================
████ OS/2 Hi, Alexander !
Replying to a message of Alexander Pototsky to All:
AP> это здесь?
AP> http://www.mb.com.ph/INFO/2001-02/IT020601.asp
Если отделить зерна от плевел, то его измышления базируются на якобы "быстром"
умении решать сравнение 2^x=1 (mod n). Упрощенно его способ выглядит следующим
образом:
x:=0; m:=0;
repeat
if not odd(m) then m:=m+n;
m:=m shr 1;
x:=x+1;
until m=0;
По существу это ничем не отличается от способа "делить 1 на 2 до тех пор, пока
снова не получится 1", схематично реализуемого так:
x:=0; m:=1;
repeat
if odd(m) then m:=m+n;
m:=m shr 1;
x:=x+1;
until m=1;
Hо я принципиально не согласен с утверждением, что какой-то из этих способов
является быстрым. В общем случае они требует порядка n операций, и никакая
оптимизация этой беде помочь не в состоянии.
Regards, ° °
Max ~
==================== End of Forward ====================
Regards, ° °
Max ~
= = QU/2 playing: Modern Talking - China In Her Eyes