Security and Cryptography
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Dev Shed ForumsSystem AdministrationSecurity and Cryptography

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old May 2nd, 2009, 05:20 PM
jmndos jmndos is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: May 2009
Posts: 1 jmndos User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 17 m 20 sec
Reputation Power: 0
Reversing rsa and obtaining p and q ?

If I have a public key and a private key, how would I reverse RSA to generate P and Q.


Can anybody provide a small example....such as if I state E, D, and N, then P and Q will be provided...

Reply With Quote
  #2  
Old May 3rd, 2009, 06:12 PM
AstroTux AstroTux is offline
Contributing User
Dev Shed Novice (500 - 999 posts)
 
Join Date: Feb 2008
Posts: 510 AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level)AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level)AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level)AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level)AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level)AstroTux User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 4 Days 6 h 20 m 43 sec
Reputation Power: 38
If you have both keys, why would you need to even try?

http://en.wikipedia.org/wiki/RSA#In...and_RSA_problem

I don't see what you are trying to achieve...

Best regards,
AstroTux.

Last edited by AstroTux : May 3rd, 2009 at 06:15 PM.

Reply With Quote
  #3  
Old May 5th, 2009, 09:56 PM
mah$us mah$us is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2009
Posts: 62 mah$us User rank is Sergeant (500 - 2000 Reputation Level)mah$us User rank is Sergeant (500 - 2000 Reputation Level)mah$us User rank is Sergeant (500 - 2000 Reputation Level)mah$us User rank is Sergeant (500 - 2000 Reputation Level)mah$us User rank is Sergeant (500 - 2000 Reputation Level) 
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!
Comments on this post
AstroTux agrees: Homework. Figures...

Reply With Quote
Reply

Viewing: Dev Shed ForumsSystem AdministrationSecurity and Cryptography > Reversing rsa and obtaining p and q ?


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump




 Free IT White Papers!
 
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.

 
Power and Cooling Capacity Management for Data Centers
This paper describes the principles for achieving power and cooling capacity management.

 
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.

 

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 




© 2003-2009 by Developer Shed. All rights reserved. DS Cluster 3 Hosted by Hostway
Stay green...Green IT