fgrieu
Reputation
34,119
95/100 score
 Jan 5 comment Proof of RSA security dependent on public key exponent I do agree with " $e=65537$ reduce the consequences of certain implementation mistakes"; in particular: no padding at all; and PKCS#1 v1.5 encryption padding with a deciphering entity susceptible to padding oracle attack by leaking information thru an error code, or timing. But, because choice of $e$ is not independent of what implementation mistakes are made, I disagree with "A standard with exponent $3$ will - on average - have weaker implementations than a standard with larger exponent". @K.G. Jan 4 comment Proof of RSA security dependent on public key exponent That's the forward search attack; but a simple proof is better than a source! $\;$ If the unknown name $x$ of a classmate is enciphered as $c=x^e\bmod N$, with $N$, $e$, $c$ known (the standard assumption in RSA encryption): simply compute $c_j={x_j}^e\bmod N$ for the name $x_j$ of each classmate; find for which $j$ it holds that $c=c_j$; the classmate $x$ is now known, that's $x_j$. This basic attack (totally overlooked in many bad introductory texts) works regardless of the choice of the public key $(N,e)$. Jan 4 comment Proof of RSA security dependent on public key exponent I recommend that you illustrate why padding is a must, using a simple example: enciphering the value of a dice throw, or the name of a classmate. Without padding, regardless of public exponent, that's entirely insecure (because anyone can test all few possible values to ascertain the right one). That's fixed with a simple random padding, where random bits or digits are added on the left of what's enciphered before exponentiation, and removed at decryption. With enough of such random padding, any valid public exponent is believed to be just fine (we have no proof, for that simple padding). Jan 4 comment Uniformly distributed secure floating point numbers in [0,1) There is the detectable characteristic (which conceivably could be an issue in some applications) that for the subset of the numbers x < 0x1p-32, the quantity x * 0x1p64 is more regularly spaced than expected for an ideally random double x in rang [0,1). In particular, for IEEE 754 double-precision floats and n<=64, x * 0x1p64 will always be an exact multiple of 1<<(64-n). Jan 4 comment Why does DES implement so much Cross Wiring? I have written a rebuttal of your guess. Jan 3 comment NIST PRIMES - cryptography The notation $a\equiv b\pmod p$ simply means that $a-b$ is a multiple of $p$. Thus for $p =\text{P-192}=2^{192}-2^{64}-1$, it holds that $2^{192}\equiv2^{64}+1\pmod p$ simply because $2^{192}-(2^{64}+1)$ is that $p$, thus is a multiple of that $p$. To prove that $2^{256}\equiv2^{128}+2^{64}\pmod p$ or $2^{320}\equiv2^{128}+2^{64}+1\pmod p$ you just need to apply that definition, and do simple algebra. Dec 31 comment TCG design specification of TPM and nonce creation There's a consequence to that requirement: the number of bits drawn from TPM RNG is fully specified; and if the TPM RNG output is known, and all its uses similarly specified, what's produced is known (except for bit order). An implementor can not e.g. get $64\lceil n/64\rceil$ bits of the TPM RNG; or/and massage the bits from the TPM RNG. Such specification makes software modules independently testable as black boxes (by replacing TRNG with PRNG or fixed balues). It also makes rigging the TPM RNG a surer way to get the thing pwned, which depending on position is a goal, or not. Dec 30 comment When/why is RSA (hybrid) encryption used rather than alternatives? @Mok-Kong Shen: I assume the "desiderata of the genre of the title line of samoz's thread" refers to using only RSA to encipher/decipher a large message. With RSA this is easy (just break the message into chunks and use RSAES-OAEP on each chunk), with a moderate size impact (like +20%), but a huge impact on performance (like x1000 or more for RSA compared to hybrid schemes, growing nearly as the cube of key size; see this). Problem is, for most applications (like, https web browsing), such a large performance impact is intolerable. Dec 30 comment Is there such a thing as a hash function with a fixed size input? @Richie Frame: the Salsa(20) core is not collision-resistant, and Bernstein insists it, or the ChaCha core, are not intended to be fixed-size hash functions. See this question. Dec 30 comment Structure for an introductory course on cryptography? Bought the book. It covers much of the fundamentals of crypto as practiced. It uses the minimum of math necessary to introduce the algorithms studied, and does so in a simple, logical, step-by-step way. I have a few reservations though: the OTP is considered a cipher; imprecise use of the notation $\mod n$; no coverage of password entropy/guessing, key stretching, Format-Preserving Encryption; limited coverage of TRNGs and their pitfalls; and a some more details. $\;$ Overall, that's easily the best introductory textbook I know for aspiring Engineering and (Information) Technology students. Dec 29 comment When/why is RSA (hybrid) encryption used rather than alternatives? @Maarten Bodewes: the question "Where RSA or any asymmetric encryption (not signature) is actually used" indeed was too broad. Hopefully the rewording is more in line with our scope. Dec 28 comment RSA Attack, known public key and ciphertext. Can decrypt the message m? If factoring $N$ was forbidden by the rule of the homework, of If $N$ was too large to factor, there is the option to try every possible plaintext, encipher it using the public key, and check against the ciphertext. Dec 25 comment Is it safe to use cipher block sizing instead of padding? Of course, the deciphering party should validate the size field: sign, maximum value. Dec 25 comment Is it safe to use cipher block sizing instead of padding? 256-bit block size, really? What cipher is this? Dec 18 comment What are the relative merits of padding algorithms pkcs7, iso7816, and x923? I know what is described here as ISO/IEC 7816(-4) padding under the name ISO/IEC 9797-1 padding method 3. It is in the 1999 (first published) edition of ISO/IEC 9797-1, and is more general as it is defined for bitstrings (with bytestrings giving what's described here); when it started to appear in ISO/IEC 7816-4 starting with the draft of the second edition, in 2000. Not coincidentally, ISO/IEC 7816-4 (2nd and 3rd edition) make reference to ISO/IEC 9797-1 for MACs, which is where it uses padding. Dec 18 comment Efficient way to confirm identity The question is now precise enough to be answered. If it gets reopened, I'll try to make an answer on the line of: since all communications are with a trusted entity, there is no reason to use asymmetric crypto. Giving each player a diversified secret key, derived from a master secret and player id, is the way to go from a technical standpoint: it's simpler, faster, with zero drawback (as long as the server can keep secrets). The hard part is distributing and keeping a secret on the player side, including from prying eyes of the player, and adversaries who compromised the player's computer. Dec 17 comment Efficient way to confirm identity Your first action shall be to define what "who" is (in "efficiently confirm who sent the request to the server"), and what credential it can have that other entities have not. In "a multiplayer game" that depends a lot on the platfrom, and how the game is distributed. This is off-topic, I'm afraid; perhaps security.SE ? $\;$Remark: with RSA used to "confirm who sent the request to the server", you would use RSA signature, and data would not be encrypted. You are right that this is compute-intensive, ECDSA would be less. Dec 16 comment RSA and difference between factors Mandating that the second highest-order bit of $p$ and $q$ is set insure that $N=pq$ has exactly as many bits as the sum of the numbers of bits in $p$ and in $q$, because $(3/4)^2>1/2$. That's not quite the way ANSI X9.31 and derivatives (including FIPS 186-4) RSA key generation methods do this; they tend to prescribe $2^{(n-1)/2}2^{n/2–100}$ where $n$ is the number of bits in $N=pq$, with $n$ multiple of $2^6$ or some higher power of two. Dec 15 comment How “hard” it is to take an e'th root mod p? Hint: apply the same math as in RSA. Dec 15 comment textbook RSA signature scheme security Indeed. Example of valid (message,signature) pairs include $(0,0)$; $(1,1)$; $(N-1,N-1)$. $\;$ Further, for $e\ll\log_2(N)$, we can set nearly the $\log_2(N)/e$ top bits of $m$ to any chosen message fragment we see fit, set the other bits to zero, set $s=\lceil\;\root e\of{m}\;\rceil$, and apply the attack in the answer to get a signature for a partially chosen $m$, which is a very practically devastating attack, rather than an existential forgery. This is not a reason to use a large $e$; this is a reason not to use plain RSA.