-2

I'm writing a script to crack small RSA keys. I've thought of a way to save massive amounts of time in the methods I'm using. To do this, I need to know how to find the largest possible prime factor of a number, of a certain size. For example:

N = 9868690954602957859
N_MAX_FACTOR_BITSIZE = 64

Then, I run N through this algorithm:

p = floor(sqrt(n))
if p mod 2 == 0:
    p += 1
while p < N:  # Referenced above
    if p mod n == 0:
        return p
    p += 2

This algorithm works on the principle that there are only two prime numbers above floor(sqrt(N)) that will divide N evenly. Seeing as both numbers will be prime, the algorithm only checks odd numbers.

To shorten the amount of time this algorithm takes, I would like to swap the N in while p < N with the largest odd 64 bit number that could multiply into N.

EG an algorithim that takes N and N_MAX_FACTOR_BITSIZE as arguments and returns the largest odd factor of N that is N_MAX_FACTOR_BITSIZE long.

The number it returns must be N_MAX_FACTOR_BITSIZE bits long.

Any help would be appreciated.

Legorooj
  • 2,646
  • 2
  • 15
  • 35
  • 1
    Can you please rephrase your question, so it were more obvious, what you want to achieve, what you already achieved and what is not working? Otherwise it looks like do-it-for-me question. – Radosław Cybulski Jun 13 '19 at 14:55
  • 3
    There is at most *one* prime factor of N greater than sqrt(N). But there might not be any. – rici Jun 13 '19 at 15:11
  • I'm working with RSA keys specifically, so there should be exactly two primes larger than `sqrt(n)` and less than `n`. – Legorooj Jun 13 '19 at 15:23
  • 3
    RSA key has nothing to do with the numerical properties. If `n` is divisible by `i` and `j`, with `i` and `j` even *relatively* prime to one another, then `i*j` must also divide `n`. If both divisors are larger than `sqrt(n)`, then their product is larger than `n`. Your premise leads immediately to a contradiction. – Prune Jun 13 '19 at 17:23
  • There are many on-line references for factoring integers, especially the unique prime factorization. We expect that you do this research before posting. – Prune Jun 13 '19 at 17:25
  • Please follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](https://stackoverflow.com/help/on-topic), [how to ask](https://stackoverflow.com/help/how-to-ask), and ... [the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. – Prune Jun 13 '19 at 17:26
  • 2
    For random integers, the easiest way to find the largest prime factor is to find the smallest prime factors first. After all the smallest factors are removed, the largest is the only one left. However, RSA moduli are chosen to be the product of two primes of approximately the same size. For these moduli the effort to find the smallest and the largest is about the same. – President James K. Polk Jun 13 '19 at 20:29
  • 1
    The easiest way is likely to call the [`factor` program](https://linux.die.net/man/1/factor). It will do the work for you, and also supports large integers. Also see [Running shell command and capturing the output in Python](https://stackoverflow.com/q/4760215/608639). – jww Jun 14 '19 at 10:53
  • look at https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation for details on RSA keys. All the pairs I have generated using PyCryptoDome and cryptography have been cracked succesfully. Also, I'm using windows, not linux. But thanks anyway! – Legorooj Jun 14 '19 at 11:24

1 Answers1

0
def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

n = 9868690954602957859

primes =prime_factors(n)[-1]

print(primes)
sahasrara62
  • 10,069
  • 3
  • 29
  • 44
  • This algorithm could possibly work with some adjustment. Will try it out. – Legorooj Jun 13 '19 at 15:24
  • This algorithm returns a list of all primes factors less than `n`. I need an algorithm that returns all prime numbers less than n and of a bitsize of `s`, or for example 64 bits. – Legorooj Jun 13 '19 at 15:36
  • @Legorooj take a look at this algorithm [Sieve_of_Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) it will help you out – sahasrara62 Jun 13 '19 at 16:23