fgrieu
Reputation
36,325
99/100 score
 8h comment Should RSA primes p and q differ in length by “a few digits”? FIPS 186-4 appendix B.3 still mandates safe primes for 1024-bit moduli (not 2048-bit); arguably, that is justified if you consider an adversary content with factoring any public moduli among many (like, to impersonate any member of a group): trying Polard's p-1 on all keys is a reasonable strategy, compared to attacking a single key with GNFS (the number of target public keys to make that workable is in the billions, I believe) 1d comment Is it possible to enumerate the possible RSA keys? In addition of otus' comment: for compression of an RSA public key, see this. Compression is not the same as enumeration. 1d comment Is a PRF applied to a secure MAC also a secure MAC? One needs some condition on the PRF's input and output size; otherwise, a PRF applied to a secure MAC could well be a much less secure MAC than the original MAC is. Even if the PRF's input and output are the MAC's output size, odds of forgery by reusing a former MAC value are slightly better for the resulting MAC than they are for the original MAC. Apr 26 comment Key size for HMAC-SHA256 @Ralph P: That seems to make sense. The weakest links are likely to be the quality of the password combined with the entropy-stretching of PBKDF2 (which is far from being the best entropy-stretching function around), the ability of the user to recognize where s/he can safely type the password, and the integrity of the device used to process the password; any of these will be incomparably weaker than 256-bit. Apr 25 comment RSA when n= 2360221 and encryption = 5 find decryption key d, when M =1234 If indeed "this was the question asked in exam" and there is no computer allowed in the exam, the right answer is: Finding private exponent $d$ is believed as hard as factorization of $n$, which is non-trivial by hand; C=1637411. Apr 22 comment Can multi-prime RSA be used to create an abuse-resistant lawful interception mechanism? @poncho: yes, using Shamir's secret sharing for the private key suffers form the problem you describe. I do not see that there's a similar issue with the last system that I propose. Sure, the shares could be meaningless, but there's a similar problem in the question's system: the RSA cryptogram could be gibberish, only trying (which requires rebuilding the private key) can tell. Apr 22 comment How secure is this logarithmic encryption algorithm? @MrCyber: if R had enough decimals, that would markedly improve, but not fully fix, the total insecurity that we have now (the minimum and maximum for R will remain a weakness allowing sizable information about M to leak from x). That would also markedly increase the size of R, which is a serious problem since we need to move Rsecretly to the receiver side. Apr 21 comment Calculating the discrete logarithm Hint: observe that $p-1$ is the product of $u=64$ and $v=19$, and $\gcd(u,v)=1$, and you know the unknowns ($\log2$, $\log3$, and $\log5$) modulo $u$ and modulo $v$; now apply the Chinese Remainder Theorem. Apr 20 comment Is the 'nonce' in bitcoin really a nonce? In cryptography, we use 'nonce' including when in legitimate use, the likelihood of reuse is low, which can be achieved by making a random choice in a large set. I do not know if that's how bitcoin uses the term. The question would be much better with a link to the authoritative bitcoin specification with the use of 'nonce' considered. Apr 20 comment Possibility for same Private Key Generation in identity-based encryption The simpler approximation $p(n)\approx{n(n-1)\over2r}$ also gives $\approx3\cdot 10^{-42}$. This is negligibly low compared to the risk of destruction of human life on earth by a comet during the forthcoming year (which is considerably more than $10^{-9}$). It would follow that the short answer is: no, there is no practical risk that well-behaving IBE servers accidentally generate the same master secret key components. Apr 19 comment How to crack unknown 8-bit encryption algorithm? I'm assuming we know the operating mode (CBC), but nothing about the 8-bit block cipher (this might be what the question is about, or not). Then, the coupon collector problem tells us that we build the full dictionary with an average 1563 bytes of known plaintext (we have a useful dictionary much before that). As pointed by @mikeaso (I guess), we can reduce this with iteratively chosen plaintext (chosing the next byte of plaintext from the previous byte of ciphertext). Apr 19 comment How to crack unknown 8-bit encryption algorithm? Assuming the question is about an 8-bit unknown block cipher in CBC mode, hint: build a dictionary of input/output pairs for the block cipher. Apr 19 comment Would A5/1 with a much larger state be a good choice of stream cipher for hardware? Define "good choice". Thomas Pornin's answer adresses cryptoanalytic security. But if very high speed is a must, producing more than 1 bit per clock with A5/1 is embarrassingly difficult; Trivium and others solve this. Other criteria (power consumption, silicon area, resistance to side channels..) exist. Apr 18 comment Integer factorization still hard with Hamming weight hypothesis? I believe that a similar trick also allows to reduce to a small set of possibilities the high-order bits of the primes. I vaguely tried to combine that on both ends to come up with a specialized version of Fermat factoring, but back-of-the-envelope (literally) scribblings have so far ended in: hopelessly slow, for 512-bit primes with 80-bits Hamming weight. It would definitely work if we lowered $h$ to something much smaller. And as the saying (attributed to the NSA) goes: attacks only get better; they never get worse. Apr 18 comment Meaning of “random n/2 bit prime length prime p” Hint: the length in bit of a positive integer $N$ (including a prime), also known as its size in bits or bit size, is the number of digits in its expression in binary with the leftmost / highest order digit non-zero. It is thus $n=\lfloor\log_2(N)\rfloor+1$, and approximately $\log_2(N)$ for large $N$. It holds that $2^{n-1}\le N<2^n$. Thus $N=3337$ has $n=12$ bits, while $107$ has $7$ bits, about half as much. Apr 18 comment State of the art low memory arbitrary-domain PRP? The problem seems to be studied, and solved, by format-preserving encryption. We have tag for that. Apr 18 comment Is the following obfuscation weak in security or not? The question could be answerable if we knew: wether the same pair $(x,z)$ is reused for several $y$; if $q$ secret or public; a definition of "too easy to break"; for certain that $(x/z)*y$ is computed modulo $q$ (and then what happens when $z$ or $x$ happens to be $q$), rather than in some other way. Apr 15 comment Can RSA-PSS signing be made deterministic without loss of security? An issue with this method is that the verifier (not knowing $k$) can not be convinced that the signature does not convey a subliminal channel. Apr 15 comment Can RSA-PSS signing be made deterministic without loss of security? I think this paper could help towards a (not fully positive) answer: J.S. Coron, Optimal security proofs for PSS and other signature schemes, in proceedings of Eurocrypt 2002. Apr 15 comment Time taken for a brute force attack on a key size of 64-bits Hints: brute force attack is trying keys, until finding one that matches. We can try them by increasing order. Trying involves one encryption with the key tried, and then a comparison of comparably small cost, and (if there's a match, that is, rarely) some confirmation operation. If a key has $b$ bits, how many possible keys are there? What's the time to try them all at a rate of $r$ keys per second? For the average time, you can compute the average of the exact time over all possible key values, or use a well-known approximation.