Thomas
Reputation
4,875
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
1 13 36
Newest
Impact
~146k people reached

• 42 helpful flags
• 365 votes cast

# 986 Actions

 Nov 18 comment special public keys and modulo n Are you talking about textbook RSA (no padding, just interpret the message as a number and raise it to an exponent) or real world RSA (with padding)? Nov 4 revised Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ typo Nov 3 comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ @fgrieu No, because we have a multiple of $p$: the modulus $n$ itself. So we get that particular prime factor "for free" by adding $n$ to the product of prime powers. Nov 2 comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ @fgrieu As I suspected (it was fairly obvious in retrospect) we also need $k$ to be non-smooth: the trick is that $n$ automatically gives us the factor of $p$, which gets us most of the way to $q - 1$ in the context of the Pollard $p - 1$ algorithm. This doesn't really change much, though, it just means that the key generation procedure needs to be adjusted to avoid $k$ being smooth, it is still open whether we can exploit the length difference between $p$ and $q$. Nov 2 revised Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ better attack, supersedes old one completely Nov 1 reviewed Approve Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ Nov 1 comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ @fgrieu Thanks! Hopefully there is a way to improve on the number theory to provide a faster algorithm to find $k$ than brute force. Nov 1 comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ @fgrieu Hmm, the square root approach seems more direct, looks like I missed the obvious! But in any case, yes, it means that subject to the restrictions the modulus has to be pretty unbalanced to offer any security, but I don't have anything better than that so far :/ Nov 1 revised Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ added 294 characters in body Nov 1 answered Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ Oct 30 comment Password generation/storage scheme Related: crypto.stackexchange.com/questions/9035/… ... and I guess basically every question containing the words "password generation", as this is hardly a novel concept Oct 29 comment Encryption algorithm designed to be easy to decrypt by machine but impractical to decrypt by hand @owlstead Yes, as long as you add any kind of nondeterminism in the scheme, that will be enough to defeat precomputation and lookup for a human without access to a computer! (admittedly the question didn't specify the exact threat model, so this may be overkill, but since we're talking about giving the computer an advantage we can be as overkill as we want :)) Oct 29 comment Encryption algorithm designed to be easy to decrypt by machine but impractical to decrypt by hand Looks like you're referring to a generic feedback scheme. CBC and CFB mode are two such schemes for block ciphers (en.wikipedia.org/wiki/Block_cipher_mode_of_operation) Oct 29 comment Encryption algorithm designed to be easy to decrypt by machine but impractical to decrypt by hand Yes, until someone precomputes the value of every letter when encrypted with that exponent and modulus, then it suffices to look up the ciphertext in a small table. To counter this, you could pack multiple letters in a single plaintext, or simply change exponents and modulus often. Oct 27 revised RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$ LaTeXified + fixed a few typos + edited tags Oct 14 comment Adding tweak to a block cipher (besides, the Skein designers had incentive to keep the Threefish key schedule as simple as possible - it needs to be run for every compression function invocation of the hash function, and the Threefish permutation itself is already not that expensive relative to its key schedule) Oct 14 comment Adding tweak to a block cipher @LightBit Correlating "simple" with "weak" is a mistake unless you have references to back up the claim for the Threefish key schedule being vulnerable to attacks. I think this is what owlstead was referring to. Oct 9 comment Breaking RSA moduli You will have to define "break" and "RSA moduli" - do you mean "factor" and do "RSA moduli" need to resist factorization, or do you mean any semiprime? Oct 8 awarded Nice Answer Oct 6 comment Is there a string that's hash is equal to itself? @fgrieu Indeed :) but it's pretty clear which answers I was referring to. +1'd your answer