Thomas
Reputation
4,107
98/100 score
 May11 comment RSA, finding p,q Correct, now how do you use this knowledge to find the factors of $p$ and $q$ efficiently? Hint: how many times can $2$ divide $p - 1$ or $q - 1$? What about $ed - 1$? With this you should be able to find an efficient way to produce a congruence of the form $a^m \equiv 1 \pmod{p}$ and $a^m \not \equiv 1 \pmod{q}$ and thus find $p$ (can you see why?) May11 comment RSA, finding p,q If you have $e$ and $d$, and you know that $ed \equiv 1 \pmod{\varphi(n)}$ - or $\mathrm{lcm}{(p - 1, q - 1)}$ - what can you deduce? May2 revised Symmetry for finite cyclic groups (Z/pZ)∗ added 315 characters in body May2 answered Symmetry for finite cyclic groups (Z/pZ)∗ May1 comment How to argue to a paranoid that RSA is safe? And using weak prime numbers is hardly RSA's fault. Apr29 comment How to argue to a paranoid that RSA is safe? Careful - while an efficient factorization algorithm implies RSA is insecure, the converse is not known to be true. In other words, it is not known (and probably false) that finding $d$ is the only way to "break" RSA. Apr25 comment FHE over the Integers - reduction to approximate gcd problem You might have been thinking of $\pi^2/6$, i.e. $\zeta(2) \approx 1.64493$... Apr23 comment How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice? @owlstead Well, OP did not specify a time limit, so he could do, say, five jumps a day and be done in under two weeks. But yes, this kind of sampling is really not guaranteed to produce a uniform distribution. Apr23 comment How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice? Dice are specialist equipment? Apr21 comment Is a tweakable block cipher still considered deterministic in nature? The use of the word "deterministic" in "deterministic algorithm" and "deterministic encryption" is not the same here, be careful not to confuse the two. In the first case is just means that given the same plaintext, key, tweak, and anything else that parameterizes the block cipher, you will always get the same ciphertext (which is obviously true), while the latter is about semantic security. So a tweakable block cipher is still "deterministic" but may be used in probabilistic encryption schemes. Are you asking how to generalize the notion of deterministic encryption to tweakable block ciphers? Apr16 comment How can I convert numbers into prime numbers? @gurghet Again, what advantage does this scheme have over using a PRNG? You can't claim it's "better" without giving any explanation, you should elaborate so future people reading this can understand why. Apr16 comment How can I convert numbers into prime numbers? What is $k$? Why the universal hashing function? I don't see how this is "better" than the standard PRNG method CodesInChaos suggested in the comments. Apr10 comment Leak-proof protocol: is such a thing possible? addendum: except if Alice sends dummy messages to pad the counter, of course, but I'm sure Bob can detect that. Apr10 comment Leak-proof protocol: is such a thing possible? If Alice and Bob can share some more state, and since transmission is 100% reliable anyway, you could keep a counter as IV - you would still achieve semantic security (with a suitable mode of operation) yet Alice would not be able to mess with the IV and inject key material in it. It seems a simpler solution than SIV-CTR, of course it doesn't solve the plaintext malleability issue - I doubt there is a robust solution in that case, since you're basically asking for a way to not allow arbitrary data to be sent over the wire, which Bob cannot distinguish since Alice and Eve share a key. Apr7 comment Is it possible to determine or estimate the period for Blum-Micali PRG? Regarding the last sentence, how exactly did you arrive at the conclusion that the OP wanted to use Blum-Micali? Seems to me he was only curious about the implications of fixed points in the permutation function. Apr7 comment Is it possible to determine or estimate the period for Blum-Micali PRG? Interesting question. The heuristic argument is obvious but I'd be interested in seeing some real (i.e. non-generic) analysis of the properties of $x \mapsto g^x \mod{p}$. Searching for "discrete logarithm fixed point" I found some references, but they all seem to focus on describing the set of primes and primitive roots with at least one fixed point, rather than a lower bound on the number of fixed points for any given $p$. Apr7 comment SHA-256 Partial Collision of initial 36 bits and more Just keep in mind that you're not going to be able to get more than 80 or maybe 90 bits colliding, so don't be disappointed if it becomes prohibitively slow - it's supposed to! But poncho's optimizations should get you most of the way there. Would you care to accept poncho's answer if it helped you, by the way? Apr4 comment Is there a technique to confirm that a given large integer value is a product of two primes? Probabilistic Rabin-Miller is $1-1/4^k$ btw Mar28 comment Near preimages, applicable to Bitcoin? @tylo I think the question was whether cryptanalysis techniques existed to improve upon brute force and thereby defeat the Bitcoin proof-of-work scheme. Mar13 comment Would a symmetric cipher with a keylength a big as the data length be information theoretically secure? @Marste Yes, that is the idea. If this does not apply then I don't think the information-theoretic properties of OTP apply either, and I doubt it applies for AES. But as I said, I am not sure of myself.