20,283 reputation
12786
bio website
location Paris, France
age
visits member for 3 years, 2 months
seen 16 mins ago

I'm an engineer with experience in applied cryptography, in particular in Smart Card systems.


Oct
9
comment Do Export Restrictions Still Apply To The Key Length of RC4?
Fine print in the wiki article says key size still matters; quoting: encryption registration with the BIS is required for the export of "mass market encryption commodities, software and components with encryption exceeding 64 bits". $\;$ Same in Europe, see e.g. REGULATION (EU) No 388/2012 OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL of 19 April 2012 amending Council Regulation (EC) No 428/2009 setting up a Community regime for the control of exports, transfer, brokering and transit of dual-use items
Oct
9
comment Bit level permutation
Hints: consider output for the all-zero input; output for the all-zero-except-one-bit input, and what it tells you about the bit-level permutation; how many such queries reveal the whole permutation; how to reduce that tremendously with slightly smarter queries; what happens with known random (rather than chosen) plaintext.
Oct
9
comment How costly is to find millions of large prime numbers for RSA?
@Willem Hengeveld: issues with your idea: $\;$ A) SHA-256 is not wide enough. That's easily fixed with a CSPRNG or KDF $\;$ B) The primes generated are distinguishable from random ones, for the expected gap from such prime to the immediately lower prime is higher. That can be fixed by incrementing by a pseudo-randomly chosen step about (say) 100 times the number of bits in the prime. $\;$ C) This is relatively slow; at the very least, sieving the prime candidates will speed-up things many-fold. $\;$ All this is sometime practiced for RSA.
Oct
9
comment How costly is to find millions of large prime numbers for RSA?
@user153465: after fixing the fact that 256-bit primes are too small (you need at least SHA-512 to get primes of size of cryptographic interest w.r.t. the RSA problem), what you are fearing when applying Willem Hengeveld's idea is so unlikely that it needs not be considered in practice (odds of a computer failure or oblivion by a comet are much higher); and if you had been looking for a mathematically exact solution (I understand that you are not), crypto.se would have been the wrong place [reposted with correction]
Oct
9
revised Breaking RSA moduli
added 45 characters in body
Oct
9
answered Breaking RSA moduli
Oct
8
comment How costly is to find millions of large prime numbers for RSA?
@user153465: by an element I mean precisely what you mean with each element (in a large set) in the text of the present question. $\;$ In the math.se question that seems to be a small non-negative integers, but if elements in the present question where actually books in html form, that's another thing.
Oct
8
comment How costly is to find millions of large prime numbers for RSA?
@user153465: Additional questions: in your actual problem, do you require that the procedure mapping each element to a prime be public (that is, does not require knowledge of a secret)? If yes, the CSPRNG technique can't use a secret key; and it will always be possible to determine if a guess of elements in the set is right. $\;$ Also, can we assimilate an element to a moderate non-negative integer (say, less than $2^{128}$)?
Oct
8
comment How costly is to find millions of large prime numbers for RSA?
@user153465: turning a randomized algorithm into a deterministic one is standard practice in crypto: we'll use a CSPRNG seeded with a secret and e.g. the index of the element to which the prime is associated. $\;$ Doing this and using a standard algorithm for RSA primes would be an easy way to solve your problem (as in the present question), save for the most efficient requirement. A standard desktop CPU would generate some hundred 1024-bit primes per second, I guess. $\;$ I'll read and ponder the math.se question.
Oct
8
comment How costly is to find millions of large prime numbers for RSA?
@poncho: That's a bit of a strange requirement given that knowledge of $p_1\cdot p_2$, and $p_1\cdot p_3$, it will be trivial to find $p_1$ (by GCD), then $p_2$ and $p_3$. $\,$ Sieve algorithms can be extended to generate primes far apart from each others; that's standard practice with regular spacing, and I do not rule out that it can be done with more haphazard spacing.
Oct
8
comment How costly is to find millions of large prime numbers for RSA?
Do you require that it is hard to guess the primes, in particular with knowledge of some of the others? $\;$ Also, is maximum efficiency thought for generating all the primes, or for generating a particular one? $\;$ I ask because we know algorithms that generate $n$ related primes with significantly lower cost than $n$ times the cost of generating one.
Oct
8
comment how to find key matrix in hill cipher
No you can't solve this problem with a single known plaintext-ciphertext pair (where plaintext and ciphertext are 3 characters): that's $3\cdot\log_2(26)$ bits worth of information, when the matrix holds nearly $9\cdot\log_2(26)$ bits of information (not quite, because it is known invertible; but close). $\;$ Again, write down what known plaintext-ciphertext pairs tell you about the unknowns; the rest will follow.
Oct
8
comment how to find key matrix in hill cipher
Welcome to crypto.se! $\;$ Your question is a straight dump of homework, and thus off topic. You are supposed to try solving the problem, and ask us only when you hit an issue, and tell us which. $\;$ As for any problem of this kind, I suggest that you 1) identify appropriate unknowns 2) identify what the givens tell you about these unknowns 3) try to apply your bag of mathematical tools.
Oct
8
comment RSA given q, p and e?
Additional hint: watch for a striking regularity in the decimal expression of the plaintext.
Oct
7
awarded  Nice Answer
Oct
7
revised Is there a string that's hash is equal to itself?
last(?) polish
Oct
7
revised Is there a string that's hash is equal to itself?
Adapt to the modifed question. Add detailed reasoning. Leave PHP nitpicking in small characters. Polish.
Oct
7
revised Is there a string that's hash is equal to itself?
Removed interrogation on what `$` at start of a string does in PHP; polish
Oct
7
revised Is there a string that's hash is equal to itself?
added 1 character in body; added 20 characters in body
Oct
7
comment Is there a string that's hash is equal to itself?
@e-sushi: I tried to answer the PHP == case, but fail to find what "allows a simple if(md5($str)===$str){echo("Oops, found one: ".$str);}", even if I change this to if(md5($str)==$str)