Shallot
Shallot copied to clipboard
katmagic
RSA key generation
Looks like you generate single RSA key pair and enumerate e (exponent) of public key as odd number between
#define RSA_PK_EXPONENT 0x10001ull
and
#define DEFAULT_E_LIMIT 0xFFFFFFFFFFull // must be odd and <= MAXIMUM_E_LIMIT
But wiki/RSA tells that oddness is not enough:
Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
Where this condition is coded?
Looks like d can not exist for equation d⋅e ≡ 1 (mod φ(n)) if gcd(e, φ(n)) != 1. So private key doesn't exists for this public key.
Right now Shallot generates 50 RSA key pairs per second. Every public key consists from two numbers: n and e. Where e can be any integer number, but it should be coprime with other special number. Shallot simply enumerates all odd e numbers.
Shallot can found e with right onion domain name but with not existing private key. So this domain will be unusable.
Yep! Enumerating all prime numbers is not simple. But we can find sequence of a lot of primes with a basic formula. This article contains most famous prime lists: http://en.m.wikipedia.org/wiki/List_of_prime_numbers
Thanks @k06a I'll start to think how best to make this patch. I'll ping you if I have any questions, if that's okay.
@k06a e doesn't have to be a prime, it only has to be coprime with the totient of n (phi). In fact, there might be prime numbers that aren't coprime to phi, and then you are introducing a new bug. (In other words, you don't know the factors of phi besides that 4 is a factor, and p and q aren't)
One correct thing to do is to look at every odd starting at EMIN, check if it is coprime to phi, and then check the hash.
I have implemented this in python in my repository.
@k06a
Actually you are kind of correct in you statements, but a little off, about the potential candidates needing to be prime. This is because any composite that is potentially coprime to phi must be the product of smaller primes which are also coprime to phi. This in turn is because any prime that is not coprime to phi must be a divisor of phi (the only factors of prime p are 1 and p, and if p is not coprime to phi then p is the only factor of p that can be shared with phi), and becuase of the fundamental theroem of arithmetic, which states that all integers are a product of primes.
So you start off with 3 (since we already know that phi is divisible by two), and then if it is coprime, you know each multiple of three is coprime. then you move onto 5, then 7, then 9 (the first odd multiple of 3 if it was coprime to phi), etc. Those are the only correct candidates for the public exponent.
So you maintain two lists, one of precomputed primes, and the other of primes which you know are coprime to phi. then skip every odd composite not divisible by any of the primes in the second list.
To do this, you need to check your known primes first, then for each odd composite starting from the smallest coprime squared.
coprimes = []
for p in primes: #primes is a small list of known primes (like all the primes under 2^32)
if phi%p: #that many primes should fit in 775 MB of RAM (4 bytes* 203280221 primes)
coprimes.append(p) #can be found in large sieve and saved to disk for reuse
check_for_good_onion()
i = 2
while i <= len(coprimes)
for ps in combinations_with_replacement(coprimes, i):
composite = product(ps)
if composite > phi:
break
check_for_good_onion()
This algorithm should skip every single non-coprime number with factors less than 2^32. That should be enough numbers to find most patterns with a single prime pair.
Looks like we can just try to find d value to determine if e is valid coprime to phi. And check this only after regexp is true for onion domain...