My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree1Thanks
  • 1 Post By Maschke
LinkBack Thread Tools Display Modes
February 1st, 2018, 03:52 AM   #1
Joined: Jan 2015
From: italy

Posts: 39
Thanks: 1

Is this a bug in RSA?

Is this a bug in RSA?

This method as described is not deterministic but can become so

in this way it works only if q = (a ^ 2 + b ^ 2) / 2 admits integer solution

an example is RSA100 of the RSA challenge

Suppose we want to factor 629

Suppose the ratio q / p < 3 -> q_max = 43

a is odd k is even always

(p*(a+k)*a)^2+(629-p*a^2)^2=(629)^2 varying a starting from 1 we see which equations admit integer solutions

a=1 NULL

a=3 NULL

(p*(a+k)*a)^2+(629-p*a^2)^2=(629)^2 , a=5

p=1258/(k^2+10*k +50)

p*k^2+10*k*p+50*p=1258 dividing everything by p

k^2+10*k-2*q+50=0 since k is even k = 2 * t


then k=2*t q=2*t^2+10*t+25

for t=1 -> k=2 & q=37

What do you think?
gerva is offline  
February 3rd, 2018, 11:52 AM   #2
Senior Member
Joined: Aug 2012

Posts: 2,139
Thanks: 623

You'll have better luck posting this to a cryptography discussion forum, perhaps
Thanks from greg1313
Maschke is online now  

  My Math Forum > College Math Forum > Number Theory

bug, rsa

Thread Tools
Display Modes

Copyright © 2019 My Math Forum. All rights reserved.