Only chars. about scallion HOT 10 CLOSED

Sorry, I missed the email notification for this because of your username.
:) I'll look at the code after work and let you know about [a-z]{16}.
Running two different instances will not duplicate work, and is the
recommended way of using two different devices.

On Mon, May 20, 2013 at 6:50 AM, forgotPassword [email protected]:

Thanks, it works :)

Questions:

[a-z]{16} does not seem to work.

Also, is running two instances on different devices (gpus) will work or
will it do the same work twice?

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/9
.

Eric Swanson
http://www.alloscomp.com/

from scallion.

thanks. meanwhile i changed DoesOnionHashMatchPattern to:

char[] num = { '\u0032', '\u0033', '\u0034', '\u0035', '\u0036', '\u0037' };
return onionHash.IndexOfAny(num) == -1;

edit:
i get 60% reported performance hit when searching for "x" vs say "xxxxxx" (i guess because array gets filled faster). i gutted the GENERATED__CHECKING_CODE since i am checking on cpu anyway and now the hit is only 40%.

from scallion.

Well, I didn't write the regex code originally, but from my reading, it
doesn't look like we support {x} for repetition. So you'd need to submit a
regexp like [a-z][a-z][a-z][a-z]...[a-z]. We should support character
classes, so you ought to be able to make that \D\D\D\D\D\D\D...\D, although
my reading of that code suggests that there might be a bug - you might need
[\D][\D]...[\D]. I remember accepting {num} was a proposed enhancement, but
freethenation and I never got around to implementing it.

On Sat, May 25, 2013 at 1:55 PM, forgotPassword [email protected]:

thanks. meanwhile i changed DoesOnionHashMatchPattern to:

char[] num = { '\u0032', '\u0033', '\u0034', '\u0035', '\u0036', '\u0037' };
return onionHash.IndexOfAny(num) == -1;

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/9#issuecomment-18451265
.

Eric Swanson
http://www.alloscomp.com/

from scallion.

ok. any thoughts as to why the performance drops for short matches? (edited-in previous comment).

also any possibility for improving the docs? i don't seem to understand from the code how the public exponent is enumerated, does it just takes it as is and only checks for sanity after a hash match?

thanks.

from scallion.

So if the match is short enough it does the check on the GPU via a lookup in a hash table. If the match is longer it does the check on on the CPU. This is done because short matches are very common and it is too expensive to send them all back to the CPU to check. Checking on the GPU has some overhead that will slow down performance but should be the same if you have one or many short regexp.

Not sure I understand your second question but we enumerate the public exponent skipping obviously bad exponents (those divisible by 2). When an exponent is found to be a match it is sent back to the CPU to be be checked by OpenSSL.

Enumerating the exponent is complicated because some of the enumeration happens on the CPU and some of the enumeration happens on the GPU. In general the process is 1) The CPU generates a bunch of base exponents 2) The GPU enumerates a large block of exponents starting at the base_exponent and stopping at approximately base_exponent + work_size*2

from scallion.

The public exponent needs to be co-prime of φ(n). So i am confused as to how you can generate a bunch of exponents without validating them. ChangePublicExponent() calls CheckSanity() but this is after the hashing is done. Am i missing something?

from scallion.

CheckSanity calls Rsa.Check which is simply OpenSSL's RSA_check_key function. We rely on OpenSSL for final verification that our key is secure.

You are correct that this is done after the hashing. It is rare that a matching hash is rejected because the exponent is not co-prime. Think about it, given two large primes, p and q what are the odds that (p-1)(q-1) is not coprime to a random large odd number e? Turns out this is a rare case and it is alot more computationally efficient to check after hashing.

from scallion.

This is what surprised me. [0] says two random numbers have odds of 61% to be co-prime. I am not sure how (p-1)(q-1) changes it.

[0] http://en.wikipedia.org/wiki/Coprime_integers#Probabilities

from scallion.

Few things 1) we tested empirically to ensure that too many hashes were not being rejected. 2) We do not test even exponents which will always be co-prime with (p-1)(q-1). Choosing an odd even pair of numbers would significantly lower the odds from 61%.

That being said, if you can come up with fast way of generating exponents that would save us from from checking co-prime exponents I would be interested.

from scallion.

It seems to work fine as is, just wanted to make sure i understand how.
I guess it is possible to factor smallest non common prime and keep multiplying by it.
Thanks. (closed?)

from scallion.