full-disclosure - Re: Rapid integer factorization = end of RSA?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <4630EFEC.9030404@infoline.su>
Date: Thu, 26 Apr 2007 22:31:08 +0400
From: "e.chukhlomin" <chukh29ru@...oline.su>
To: xxx xxx <kaharas@...il.com>,  full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

xxx xxx wrote:
>
>     Lemma:
>     p*(-q)=p*q*(-p)
>     and respective:
>     (-p)*q=p*q*(-q)
>     Proof:
>     p*(-q)=p*(N-q) - by the data, then
>     p*(-q)=p*(p*q-q)=p*pq-p*q=p*q*p-p*q=(p-1)*(p*q)
>     (-p)*q=q*(N-p) - by the data, then
>     (-p)*q=(p*q-p)*q=p*q*q-p*q=p*q*q-p*q=(q-1)*(p*q)
>     Q. E. D.
>
>
> Like  Stanislaw said before be,  this Lemma is  obvious. You're
> saying that 0=0, and man, this is a thautology!
> You ask why? let N = p*q.
> Then,
> p*q = 0 mod N
> Now, let be -1 the opposite of the unit ( usually called e...)
> 0 = (-1)*0 = (-1)*p*q = (-1*p)*q = (-p)*q
> 0 = 0*(-q) = p*q*(-q)
>
>     Gypothesis:
>     Let N = p*q = A1*B1 + A2*B2... + An*Bn
>     Then exists some subset(A1...An) and respective subset(B1...Bn),
>     which
>     satisfies for equality:
>     A1*(-B1)+A2*(-B2)...+An*(-Bn) = p*(-q)=p*q*(p-1)
>     or
>     A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)
>
>
> This is another obvious thing!
> if N = sum(A_i*B_i), then
> -N = -1*N = -1*sum(A_i*B_i) = 0 mod N
> and, for the distributive propeties,
> -1*sum(A_i*B_i) = sum (-1*A_i*B_i) = 0 mod N
> 
>
>     If found such (A1...An) and (B1...Bn), we can find p or q by
>     dividing
>     p*(q-1) on p*q:
>     p*(q-1)=p*q*(p-1) => (p*(q-1))/(p*q)=(p-1) => (p-1)+1 = p
>     or
>     (p-1)*q=p*q*(q-1)=>((-p)*q)/(p*q)=(q-1) => (q-1)+1 = q
>
>
> Here there's a mistake: p*(q-1) != p*q*(p-1) mod N. in fact, let N =
> 2*3.
> 2*2 = 4 ! = 6*1 = 0!!!
> Beeing this assumption wrong, all the remaining demostration is
> obviously false...
>
ok, if your consequences are right, could you disprove this gypothesis?

Gypothesis:
Let N = p*q = A1*B1 + A2*B2... + An*Bn
Then exists some subset(A1...An) and respective subset(B1...Bn), which
satisfies for equality:
A1*B1+A2*B2...+An*Bn = p*q and:
A1*(-B1)+A2*(-B2)...+An*(-Bn) = p*(-q)=p*q*(p-1)
or
A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)

in terms of this gypothesis, could you really prove: there are no one
subsets (A1..An) and respective (B1...Bn) which satisfies equality:
A1*(-B1)+A2*(-B2)...+An*(-Bn) = p*(-q)=p*q*(p-1)
or
A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)
?

Another example in terms of gypothesis:
35 = 2^2*2^3 + 2*1 + 1
then one of possible subsets of 35 is: 4*8 + 2*1 + 1 (4,2,1) and (8,1,1)
try one of possible cases for test subsets (A1...An) and (B1...Bn):
4*(35-8)+2*(35-1)+1*(-1) = 4*27 + 2*34 + 1*(34) = 108 + 102 = 210
then, 210 / 35 = 6
6+1=7
gcd(35,7)=5
Gypothesis is right (or written above is exception?)
Your sample: 6 = 4 + 2 => 1*4 + 2*1
1*(6-4)+2*(6-1)=12
Divide result by 6: 12/6 = 2
Add one for 2: 2+1 = 3
Test: gcd(6,3)=2

Any other samples needed?

More over, while no one present valid proof of incorrectness, it is
correct, right?
<Link.asp?CardId=69;6e;63;6f;72;72;65;63;74;6e;65;73;73;0;4c;69;6e;67;76;6f;55;6e;69;76;65;72;73;61;6c;20;28;45;6e;2d;52;75;29>
Has somebody more constructive ideas?


Content of type "text/html" skipped

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/