Discuss Reversing rsa and obtaining p and q ? in the Security and Cryptography forum on Dev Shed. Reversing rsa and obtaining p and q ? Security and Cryptography forum discussing issues related to coding, server applications, network protection, data protection, firewalls, ciphers and the like.
We cover the world of technology
like no one else, constantly updating you with the best information
available on open source software, Microsoft technologies, hardware
and news from around the world.
Posts: 62
Time spent in forums: 1 Day 5 h 7 m 33 sec
Reputation Power: 19
As AstroTux observed, this question is only of theoretical interest, unless your cryptography professor has assigned it to you as a problem (hint, hint).
Given n as the modulus, and exponents d & e, this python function returns the factors of n as an array:
Code:
def rfact(n, e, d):
""" because e*d is congruent to 1 mod phi(n), e*d is very close to
being a multiple of phi, and phi is very close to n for an RSA
modulus - so the whole number quotient (e*d)/n is 1 less than
this factor """
k = 1 + (e * d) / n
phi = (e * d - 1) / k
""" if n=p*q, then phi(n) = (p-1)*(q-1) = p*q + 1 - (p+q); but p*q=n,
so phi(n) = n + 1 - (p+q); set 'sum' to p+q """
sum = n + 1 - phi
""" we now know the product of p and q (n) and their sum (sum). we
solve for p and q using the quadratic formula. set 'delta' to
the radical in the numerator of the formula """
delta = isqrt(sum**2 - 4*n)
p = (sum + delta) / 2
q = (sum - delta) / 2
if p*q != n:
print '!Failed: modulus not factored correctly!'
return [p, q]
Function rfact() requires this integer square root function:
Code:
def isqrt(n):
# construct an initial guess value
d = len(str(n)) # count of decimal digits
x = '3'
d = d / 2
while d > 0:
d = d - 1
x = x + '1'
x = int(x)
# perform Newton-Raphson iteration
prev = 0
while x != prev:
prev = x
q = n / x
x = (x + q) / 2
return x
On my old 1.8 GHz Thinkpad, a 1024-bit RSA modulus takes about 350 microseconds to resolve.
DISCLAIMERS: 1) This code is offered without any warranty. If your computer catches fire when you try to run it, don't say I didn't warn you. 2) If you don't know how to run python code, search the interwebs: tons of python info!
How to Present Effectively Online This white paper offers practical and actionable advice on the key steps that any presenter should consider as they plan and execute a Webinar or online meeting.
Open Source Security Myths Open Source Software (OSS) is computer software whose source code is available to the general public with relaxed or non-existent intellectual
property restrictions (or arrangement such as the public domain), and is
usually developed with the input of many contributors.
Scalable, Fault-Tolerant NAS for Oracle - The Next Generation For several years NAS has been evolving as a storage alternative for Oracle databases, and for good reason: NAS is quite often the simplest, most cost-effective storage approach for Oracle. Learn about the benefits that HP's approach to scalable NAS brings to Oracle environments in this comprehensive white paper.
Understanding Web Application Security Challenges This white paper discusses many common threats and preventive measures for Web application security, and explains what you can do to help protect your organization.