20,355 reputation
12787
bio website
location Paris, France
age
visits member for 3 years, 2 months
seen 10 hours ago

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


Oct
15
comment Is there any existing cipher capable of scaling from a 1 bit key up to a one-time-pad?
The criteria that given ciphertext and $b$-bit key, $2^b$ distinct plaintexts are possible $\;$ a) Can not be reached at all for key/plaintext ratio above 1, even though that is considered in the question. $\;$ b) Is NOT enough to give a useful level of confidentiality for other ratio (proof: consider encryption by XOR with key padded with zeroes up to plaintext length); that criteria can however be a compatible addition to more standard security criteria, at least if we allow about $2^b$ possible distinct plaintexts.
Oct
15
comment Is there any existing cipher capable of scaling from a 1 bit key up to a one-time-pad?
Note that the one-time-pad is not a cipher, by the modern definition, which requires key size to be fixed for arbitrary or much larger plaintext size. $\;$ I know no existing algorithm answering the question. It seems feasible to build one from existing primitives, but exactly what would be the desired security criteria?
Oct
15
comment Encrypted read-only message queue
Also: because RSA allows fast signature verification, it is a good candidate for the signature from an efficiency standpoint if reading and forwarding with integrity verification largely predominates writing/signing. If signature size overhead is an issue, RSA signature with message recovery can help reduce the signature overhead (e.g. to 34 bytes with ISO/IEC 9796-2 scheme 3 using SHA-256, with encrypted message of at least 222 bytes and 2048-bit RSA). $\;$ AES-CTR encryption/decryption is fast, and its size overhead is limited to the IV (e.g. 10 bytes for a counter to $2^{80}$).
Oct
15
comment Encrypted read-only message queue
Yes. The key for encrypting and decrypting the messages can (and should) be that of a symmetric algorithm, e.g. AES-CTR with suitably random or sequential IV, and known to groups 1 and 2. $\;$ Signing should be on the enciphered data, using an asymmetric signature algorithm (e.g. RSA with PKCS#1v2 signature padding), with the private key known to members of group 1, and the public key known to all (as implied by its name). $\;$ Everyone (except possibly from group 3) should verify signature of enciphered data manipulated.
Oct
15
comment Are LFSRs enough for this?
@mpr: I tried to address your comments in the answer, including generalizing to $m$ consecutive colluding players. $\;$ Notice that I have made no statement whatsoever about when we are safe, thus have not answered the question asked in the above comment.
Oct
14
comment Is it true the longer the key length is the more secure the encryption?
I do not think that "under certain kinds of attacks AES-256 is actually easier to break than AES-128": the increase in key size gives much more security, thus not $2^{128}$ times more.
Oct
14
comment Are LFSRs enough for this?
I do not think that my first comment needs to be incorporated in the question. $\;$ Is it correct that the adversary knows the value on every ticket, and wants to assign which ticket was generated by which player, with odds better than random?
Oct
14
comment Are LFSRs enough for this?
On the problem: Are the experimenters that collude with the adversary capable of $\;$ a) telling which number they drew? $\;$ b) telling exactly when they pressed the button? $\;$ c) pressing the button at a chosen instant?
Oct
14
comment Are LFSRs enough for this?
Incidentally: we know how to tweak an LFSR with a primitive polynomial of degree $b$ into a generator with almost identical output save for an extra 0, making the period $2^b$ rather than $2^b-1$, and insuring that the generator can't become stationary when complemented; see this.
Oct
10
comment How does MD5 process text which is shorter than 512 bits
Take care that MD5's endianness is quite pervert. The encoding of bits in bytes is big-endian (as shown by the fact the padding byte is 0x80, not 0x01), but the encoding of bytes in 32-bit words is little-endian. $\;$ IIRC, in the landmark paper with the first MD5 collision there was some endianness issue in the first version, and that needed the collision search to be performed all over again.
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
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.