Results 1 to 7 of 7

Thread: rsa Questions

  1. #1
    tommychong
    Guest

    rsa Questions

    .i was wondering if it is not feasable to find the common denomanator whith 2 large pirmes
    Last edited by tommychong; September 6th, 2005 at 20:16.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    tommychong
    Guest
    bad Queston so i edit
    Last edited by tommychong; September 7th, 2005 at 04:49.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  3. #3
    Administrator dELTA's Avatar
    Join Date
    Oct 2000
    Location
    Ring -1
    Posts
    4,206
    Blog Entries
    5
    Are you trying to find a common denominator for two primes? The thing with primes is sorta that they don't have any denominators at all you know...

    And if we're not talking primes, you should try LCD instead of GCD.

  4. #4
    tommychong
    Guest
    thanks fella i guess i sound like a retard but yes the lowest common is what i need.say if i found away to turn every rsa modulo into 2 numbers and the LCD=Q. is it too hard to compute the LCD of say 600 byte numbers?it seems almost as hard to compute as factoring no?because if it cant be done i really dont wanna spend the time learning c++
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    Administrator dELTA's Avatar
    Join Date
    Oct 2000
    Location
    Ring -1
    Posts
    4,206
    Blog Entries
    5
    Yes, it should be equally hard (complexity-wise) to find the smallest factor and to factor it completely.

  6. #6
    tommychong
    Guest
    yea i was reading on attacking rsa and in one of the attacks it said that sometimes if you can find the common dennomonator of the 2 modulo that you would break there system.But from what i can see it is not posible for me on my 2800 to find the lcd of 2 huge numbers
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  7. #7
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    I think you're confusing a few different things. There's

    Greatest Common Divisor gcd(a,b), the largest number that is a factor of both a and b. When a and b are both primes, then gcd(a,b) = 1.

    Least Common Multiple lcm(a,b), the smallest positive number that is divisble by both a and b. When a and b are primes, their least common multiple is a*b.

    Lowest Common Denominator. This is really the same thing as lcm. When you are trying to add two fractions a/b and c/d by hand, one way to find the answer is (ad+bc)/bd, but this often leads to large denominators. One way to keep numbers small is to multiply through first with lcm(b,d) and then divide it out again.
    Example:
    First method: 1/6 + 1/9 = (1*9+1*6)/(6*9) = 15/54 = 5/18
    LCM method: lcm(6,9)*(1/6 + 1/9) = 18/6 + 18/9 = 2+3 = 5 => 5/18

    Both LCM and GCD are easy to compute given the product n=a*b of two primes.

Similar Threads

  1. 2 Questions
    By DaBookshah in forum The Newbie Forum
    Replies: 5
    Last Post: November 2nd, 2006, 09:06
  2. Some DRx Questions
    By Lenus in forum OllyDbg Support Forums
    Replies: 3
    Last Post: December 31st, 2004, 04:19
  3. Some DRx Questions
    By Lenus in forum The Newbie Forum
    Replies: 2
    Last Post: December 28th, 2004, 18:11
  4. ??? Questions ???
    By Anonymous in forum OllyDbg Support Forums
    Replies: 4
    Last Post: July 23rd, 2003, 14:52
  5. RegOrganizer 1.3B4: Questions and More Questions (sv / +spl/\j guru!)
    By foxthree in forum Malware Analysis and Unpacking Forum
    Replies: 17
    Last Post: March 9th, 2002, 06:43

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •