965 reputation
319
bio website
location
age
visits member for 1 year, 6 months
seen Jan 10 '13 at 13:25

Nov
14
comment Efficient set up for a Montgomery multiplication
@mikeazo: I said you're correct and also +1'd your comment as it is indeed one way to solve the thing. But you know how it is in today's world: you spare every single bit that you can :D Also, the computation of $R^2 \mod N$ must be performed each time the modulus changes, so depending on the setting, this can happen often and might not be easily precomputed.
Nov
14
comment Efficient set up for a Montgomery multiplication
@mikeazo: This is one way to do it, of course. But it is not efficient as it requires a true multiplication mod $N$ whereas the purpose of Montgomery's multiplication was to be more efficient. Hence, although the cost for it gets lower with the number of Montgomery multiplications performed in this representation, one wants to reduce it if possible.
Nov
14
comment Efficient set up for a Montgomery multiplication
@B-Con: I'd say as much as Montgomery multiplication has: I'm not sure if there are many other settings where one wants to compute modular exponentiations with a modulus of 4096 bits :D
Nov
9
comment Randomized algorithms and the one time pad
If one think of the key as the whole set of pads, as described above, there is no problem at all provided you always pad the same message with the same pad. (The only problem is that "standard one-time pad" does not really specify what happens when you come to encrypt the same message twice.) The resulting scheme will be semantically secure, assuming the events from your dice are uniformly distributed. (I'm actually thinking of such truly random pads in the example scheme defined above.) Still, the resulting encryption algorithm is fully deterministic (not randomized/probabilistic).
Nov
8
comment Randomized algorithms and the one time pad
@PaĆ­loEbermann: Indeed, thank you.
Nov
8
comment Randomized algorithms and the one time pad
@John Deters: You're correct. This is why I stressed that one-time pad does not fit the framework. I'll change the wording accordingly. Thanks.
Nov
8
comment Randomized algorithms and the one time pad
@fgrieu: I fail to see what you mean by "difficult goal". A randomized algorithm can be used for any kind of goal. Although it is true that they are often the only known algorithms to efficiently solve some difficult problems, it is also not known that there cannot always be a deterministic algorithm solving the same problem at least as efficiently. Also, in your example, the randomized version for factorization you give is less efficient than the deterministic one. I guess this comes from the typical representation of an attacker as a probabilistic polynomial time algorithm.
Nov
8
comment How can I use eulers totient and the chinese remainder theorem for modular exponentiation?
To do the computations, you use what is the most efficient: -1 or 4. For instance, I'd compute the $5^7 \mod 11$ above as $5^{-3} \mod 11$ instead. (As $5^3=4\mod 11$ and $4\cdot 3=1\mod 11$, $4^{-1}=3\mod 11$.) For a mathematician, there's an equivalence class, the label does not really matter, although common practice is indeed to use non negative numbers.
Nov
8
comment Randomized algorithms and the one time pad
The standard naming, coined by Goldwasser and Micali, is probabilistic encryption.
Nov
3
comment Why does HOTP use such a complex truncate function?
You meant from $2^{80}$ to $2^{16}$.
Oct
30
comment Modifications of CBC-MAC
A message of length bigger than $2^n$ does not exist :D This is forbidden by the format constraint. (You've to understand that the actual limit value is not crucial: you could also take a limit of $2^{2n}$ and code the bit length over two blocks, this would achieve the same effect.)
Oct
29
comment Modifications of CBC-MAC
@Avery: the constraint on the message format prevents a valid message from being extended into another valid message by a simple append.
Oct
29
comment Can a proof be constructed to show there is no distinguisher?
The hash function Skein is not exactly what I would call "simple" from the point of view of understanding the way it maps its inputs to outputs. Otherwise, one would "simply" find pre-images and collisions for it!
Oct
29
comment Modifications of CBC-MAC
It is correct that any $\rho\neq0$ will do. However, there was a reason: the adversary in 1) cannot be distinguished from the real signer and that it is straightforward to show it. (Of course, it might also be the case with other ways to choose $\rho$, but harder to prove.) Note that it was never stated in the question that the adversary has to be indistiguishable from the legitimate signer, but this is a nice property (from an attacker point of view) as it shows that forgeries cannot be detected.
Oct
28
comment Why do we need in RSA the modulus to be product of 2 primes?
@fgrieu: nice link. It might be worth noting that the encryption scheme also "works" with $N=p$ a big prime, but then becomes symmetric (and was actually invented by Polhig and Hellman) as opposed to RSA which is an asymmetric one.
Oct
23
comment One time pad key exchange
Well, I construe one time pad as a pad that you use one time. Please also note that the distinction you're trying to make is already part of the answer: sequences thus genereated are "only" pseudo-random. Also, you'll have a hard time defining what a perfectly random string is in practice: anything that you'll use to generate it has some bias...
Oct
22
comment Could the Enigma algorithm be classified as a Feistel network?
@JohnDeters: I'd be interested in your definition of a stream cipher and a block cipher then. (You might have noted the caveat in my previous comment that the view I have of a stream cipher might not be universally recognized; but at least I gave one.)
Oct
22
comment Hash function from narrower block cipher operated in CBC-encryption mode?
@fgrieu: you are correct that the case $n>1$ cannot be attacked since the key after first round was the same for both messages and due to the bijectivity of the block cipher, a collision could not occur. I updated the last paragraph accordingly. As I write, I'm concerned about the small "bandwidth", and there is probably a lot to do, but would require some more time.
Oct
20
comment Shamir Secret Sharing - Threshold decryption implementation
The polynomial $f$ underlying Shamir's $(t,n)$ secret scheme is such that it has degree $t-1$ and $f(0)$ is the key (or secret) to be shared. The share given to participant $i$ is $f(i)$. You can compute $f$ using Lagrange interpolation from $f(j)$, $j=0,...,t$. See also section 2.1 of the paper linked in the answer above.
Oct
19
comment Using pairings to verify an extended euclidean relation without leaking the values?
The exact definition of the $P_i$, $q_i$, and $s$ are not really relevant to the question. But in case you really want to know the dirty details, look at the dirty details of set intersection queries...