Reputation
24,522
Next tag badge:
106/100 score
19/20 answers
Badges
2 32 103
Impact
~356k people reached

2h
comment Rabin-Williams, blinding and size of Integer r?
It is not that blinding was not enough to stop key recovery. In the attack, blinding enabled key recovery, because of an implementation bug. That's a problem with RW signature: goof in the Jacobi, or let a multiplicative forgery due to padding creep, and the public modulus is effortlessly factored; in RSA, there are less goofs that can cause this.
2h
comment How multiplicative property of RSA can be exploited
@111: Just hashing the message using e.g. SHA-1 is not quite enough protection for signature; and you can't replace the message with its hash for encryption, for then it can not be efficiently deciphered. $\;$ It remains that indeed, RSA encryption and signature schemes used in practice do not externally have the multiplicative property.
10h
comment Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?
@CodesInChaos: I did the math (it needs a check), and come to the (tentative) conclusion that the method proposed in the question, at least slightly modified to increase the iterated function width $w$ to at least $b$ (64 for DES) rather then $n+1$ (57 for DES), is a significant improvement over MitM with partition into plausible number of runs. However it is far from achieving what's in the above comment, and even the best improvements known do not seem to approach that; my guess is that somewhat you overestimate success odds or underestimate the number of DES operations required.
11h
comment How the couples of int (n,e) and (n,d) are converted into char for RSA public and private keys?
That question is closely related to this one. $\;$ The formatting of RSA key files is system-dependent, thus off-topic. $\;$ As an aside in $(n,d)$ and $(n,e)$ the modulus $n$ must be composite, and both $d$ and $e$ must be less than $n$ in all standard formats; $(5,7)$ breaks both of these requirements.
13h
comment Why does applying 56-bit DES twice only give 57 bits of security?
@CodesInChaos: After studying (and tentatively answering) your question: indeed, distinguished points/cycle finding can help reduce memory requirement, including with known plaintext, more than obvious partitioning of the work does, even if that's still at the expense of more DES operations. I now have some better understanding of how. $\;$ Somewhat the context of the question had me totally stuck to things with cost near $2^{57}$, hence my overlook of what you had in mind. Thanks !
15h
comment Creating of finite field over small prime number for Elliptic Curve
Highlighting potential abilities of some particular combination with catchy name of virtual machine, language, compiler, and libraries, is squarely off-topic. Even small Elliptic curves in $\mathbb F_p$ with $p$ small (as in $p=23$, or even $p=1152937390550679040294931$) are only borderline topical, sine such parameters do not lead to cryptographically secure cryptosystems.
16h
comment Creating of finite field over small prime number for Elliptic Curve
Ah, the problem of determining the number of points on the curve more efficiently than by the trivial algorithm of explicitly finding+counting all the points would make a different, and more acceptable question, especially if you remove/dampen the request for code. Would you edit the question in that direction?
18h
comment Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?
It would help to name the block width of $E^{(1)}$ and $E^{(2)}$, say $b=64$ in the case of DES; and state how from these $b$ bits we determine the $n+1$ bits kept for the iterated function, which is not trivial.
19h
comment Why does applying 56-bit DES twice only give 57 bits of security?
@CodesInChaos: As is, this attack is not really much work only on an hypothetical computer with at least $2^{59}$ bytes of memory (like 500 times the total RAM on the 80,000 CPUs in the current top supercomputer of the TOP500). Otherwise said, as is, it is purely theoretical. $\;$ That why I'd like to understand what you have in mind.
19h
comment Creating of finite field over small prime number for Elliptic Curve
This is obviously homework (and easy one); just do it, that's how you'll learn! Hint: start by exploring all x and y, and keeping the approriate ones. Then, when that becomes too slow, compute y from x as a square root modulo p.
1d
comment How to securely map an element from an smaller domain to the other element in a large domain
The previous comment makes a convincing argument that if $e$ can be guessed, and $Enc_{pk}(r \cdot e)$ known, and $Enc_{pk}$ is homomorphic, and $e^{-1}$ in the sense of the homomorphism can be computed from $e$, then $Enc_{pk}(r)$ can be successfully guessed. While this is far from the question as written (which does not mention anything like homomorphic, or multiplication by $r$, or that this is random), my conclusion is that what's asked in question and comments can't be achieved.
1d
comment How to securely map an element from an smaller domain to the other element in a large domain
I have trouble relating the above comment to the question. $\;$ In particular, is the " small sized domain " of the question that of $r$, $e$, or $v$ in the comment? Is the " public encoding " of the question the " Paillier encryption " of the comment? Also, what is meant by " eliminate $e$ " in that comment? I suggest reformulation the question, incorporating the comment in a unified framework.
1d
comment Non adjacent form of an integer is unique
@Vi Jay: Yes, your summary is correct. The answer now gives more details on the general method, called infinite descent , a special form of proof by contradiction. $\;$ Also I revised the proof. Formerly I used $b=(a−1)/4$ in the second case of the second proof, in order to match the first proof, but that left a gap because I assumed without proof that small $a$ had a single NAF. Now I'm first proving that $0$ has a single NAF, and in the second case of the second proof use $b=a−1$, which is simplest. $b=(a−1)/2$ also works.
2d
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
@Ricky Demer: We also need that " different users " bit.
2d
comment How to securely map an element from an smaller domain to the other element in a large domain
With the requirements as I understand them, and the addition that the encoding/mapping is a deterministic function (in addition to public), there is no solution, for precisely the reason given in mikeazo's comment.
2d
comment How to securely map an element from an smaller domain to the other element in a large domain
Anything wrong with simply: each user $j$ secretly chooses a 256-bit random secret key $K_j$, then computes the 256-bit $\operatorname{HMAC-SHA-256}(K_j,x)$ where $x$ is a $s$-bit element of the small domain? $\;$ Perhaps that does not match the "public encoding" requirement, even though the method is public?
2d
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
There's a solution to the problem even if $E_{pk_D}$ is secure, thus randomized, which is assumed in any sound application of public-key encryption. That seems to be the intend in the textbook: no mention is made of RSA; much less of textbook RSA, which would not be able to directly encipher or sign a sizable database query, sign an RSA cryptogram, or encipher a message comprising an RSA signature, assuming $k_A$ and $k_D$ have the same size. $\;$ $\;$ Additional hint: the policy is worded with "A user" rather than "Anyone".
2d
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
Hint: assume that an answer counts as information about what was asked. $\;$ Note: one method clearly beats the other, but both have the pitfall that the length of $R$ (and of the answer) is not masked, which is information about what was asked. $\;$ Note: You should probably retype and reword the question more concisely, in particular because there is a chance that you'll find the solution doing so; at least, give credit to the textbook (the question is interesting), and verify that you have the right to repost this extract.
2d
comment what is number of invertible matrix m*m on$ z_n$?
The question is in fact a duplicate of this one, which has a satisfactory solution (if not answer in the sense of the CSE website logic) in comment, and as an edit of the question.
2d
comment what is number of invertible matrix m*m on$ z_n$?
@Ricky Demer: the OP gives a hint with the tag hill-cipher, which indeed uses as key an invertible $m\times m$ matrix with elements in $\mathbb Z_n$.