20,490 reputation
12788
bio website
location Paris, France
age
visits member for 3 years, 2 months
seen 39 mins ago

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


Oct
22
comment Small Prime Difference in RSA
@ddddavidee: as far as I can tell, the only difference is that your $l$ is mikeazo's $\frac{p-q}2$
Oct
21
comment Small Prime Difference in RSA
It is correct that "The difference between $p$ and $q$ should not be small"; however, under the assumption that $p$ and $q$ are randomly seeded and appropriately large for cryptographic use, odds are entirely negligible that the difference between $p$ and $q$ is dangerously small. So much that the (often mandated) check that$|p-q|$ is above some limit really is useful only as an additional check that said assumptions hold, and to reassure those who do not trust math.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
@user153465: indeed, to answer Question 1 by the affirmative, we need to replace arbitrary value in $Z_n$ with random in $Z_n$ (as Poncho did), or chosen in $Z^*_n$ without knowledge of the factorization of $n$ (as I did). $\;$ Question 2 as currently worded is not answerable by yes or no until both this and secure are better defined.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
Rephrased without a question mark: $\;$ Show that if $m$ has a multiplicative inverse in $Z^*_n$, then $f: r_1\to f(r_1)=r_2=r_1\cdot m\bmod n$ is an injection from $Z^*_n$ to itself. $\;$ Show that if an $m$ chosen in $Z^*_n$ without knowledge allowing the factorization of $n$ had sizable odds of having no multiplicative inverse, it would be easy to factor $n$. $\;$ Conclude about what we can safely assume about $f$ (noticing $Z^*_n$ is a finite set); then about what that implies for $r_2$ if $r_1$ is uniformly random.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
I hope Got is in the past tense. $\;$ My hint allows an easy proof. Find it, and you'll be able to solve many similar exercises.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
Hint: What is the condition making $f: r_1\to f(r_1)=r_2=r_1\cdot m\bmod n$ a bijection over $Z^*_n$? $\;$ And how likely is that condition assuming $m$ is defined without knowledge allowing the factorization of $n$?
Oct
20
comment Serpent 256bit key wrong round keys
The Serpent Proposal, top of page 7 defines $w_{−8}\dots w_{−1}$. That allows applying $w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus i)\lll 11$ including for $i=0\dots 7$. $\;$ Please fix the question accordingly, and tell us if any issue remains. $\;$ Also: use $\TeX$, that's easy! Your formula is written $w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus i)\lll 11$.
Oct
18
comment What is the history of recommended RSA key sizes?
[reposted with correction] As of the embedded world: one of two RSA keys with 321-bit public modulus has been used by French banks as global keys for static issuing certificates of credit/debit Smart Cards, well after the end of the 20th century (but are phased out now). See references in the third bullet point of this answer. The lowest routinely used nowadays is more like 1024-bit (e.g. European tachograph cards).
Oct
17
comment How secure would HMAC-SHA3 be?
@Richie Frame: the Keccak submission (and NIST slides I just added) seem to use the bitrate $r$ as block size, without the at least as large as $c$ condition that you suggest. I am without informed opinion.
Oct
17
comment What is the history of recommended RSA key sizes?
One data point: the original (1974) RSA paper said: "We recommend that $n$ be about 200 digits long." That was about 664 bits.
Oct
17
comment Compare two approaches for cracking RSA key
@Samuel Judson: for the first part, you have the right order of magnitude, but a) the number of 1536-bit primes is about half of what you estimate; b) what's the lowest possible value for the highest of the two primes? That allows another significant reduction. $\;$ For the second part, you have given an order of magnitude of the effort involved in generating the key. The question asks to turn this into a factorization method for the key at hand, without assuming prior knowledge of the password. $\;$ Side hint: the part of the answer reading "We'll have to do this twice" is wrong.
Oct
16
comment Are LFSRs enough for this?
I now have a tentative conjecture about a safe setup, with the colluding players never consecutive, and separated by $h$ honest ones.
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?