3,961 reputation
1730
bio website
location Wellington, New Zealand
age
visits member for 3 years
seen 6 hours ago

I am an undergraduate computer science and mathematics student in New Zealand. My fields of interest are computer graphics, in particular the physics of light transport, and to some extent cryptography, as well as programming and software development in general.


May
15
comment RSA private exponent primality
Specifically, $d$ is going to be an integer such that $ed - 1 = k\cdot \mathrm{lcm}(p - 1, q - 1)$ for some integer $k$, that is, $d = \frac{k \cdot \mathrm{lcm}(p - 1, q - 1) + 1}{e}$, so, really, its prime factorization could be anything, except it will always be coprime to $\mathrm{lcm}(p - 1, q - 1)$, that's about all you can say.
May
15
comment modulo operations in crypto algorithms
@user220201 This is when, e.g. using $e = 3$, we have $m < n^{1/3}$, in which case $c$ is literally $m^3$ and you can just take the cube root in the integers and decrypt the ciphertext using only public information. If $m > n^{1/3}$, then we only know that $c + kn$ is a perfect cube for some integer $k$, but this $k$ becomes very, very large on average as $m$ increases (with a very complicated distribution), making it impossible to brute force it without knowing the factors of $n$ (or so we believe).
May
14
comment RSA private exponent primality
The public exponent doesn't have to be a prime.
May
12
comment Generating unsigned, bounded random value using signed bounded random values
"All generated random values must have a normal distribution" is a non-issue, once you have a uniform distribution you can convert it to a normal distribution efficiently via inverse-transform sampling or specialized methods like Box-Muller. Focus on getting a uniform distribution (rejection sampling will probably be fast enough, except perhaps for pathological values of $x$).
May
11
comment RSA, finding p,q
If you prefer, you can use the following idea: since $ed - 1$ is a multiple of both $p - 1$ and $q - 1$, if follows that $a^{\frac{ed - 1}{2^k}} \equiv \pm 1 \pmod{p, q}$ for some small $k$. Thus trying a bunch of random $a$'s, you will quickly find an $a$ which is a quadratic residue modulo $p$ but a quadratic nonresidue modulo $q$, such that $a^{\frac{ed - 1}{2^k}} - 1$ is a multiple of $p$ but not of $q$, and you are done.
May
11
comment RSA, finding p,q
I'm not sure I follow what you mean by "2 divides p - 1 ϕ(p-1) times", but the basic idea is this: if 2 divides $p - 1$, $x$ times, and 2 divides $q - 1$, $y$ times, then 2 divides $ed - 1$ at least $\max(x, y)$ times. So if you keep dividing $ed - 1$ by 2, at some point you will end up with a number that is a multiple of $p - 1$ but not of $q - 1$ (or vice versa). Then using Fermat's little theorem can produce a factor of $n$ (there are some details but that is essentially the idea).
May
11
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?)
May
11
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?
May
2
revised Symmetry for finite cyclic groups (Z/pZ)∗
added 315 characters in body
May
2
answered Symmetry for finite cyclic groups (Z/pZ)∗
May
1
comment How to argue to a paranoid that RSA is safe?
And using weak prime numbers is hardly RSA's fault.
Apr
29
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.
Apr
25
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$...
Apr
23
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.
Apr
23
comment How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice?
Dice are specialist equipment?
Apr
21
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?
Apr
16
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.
Apr
16
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.
Apr
10
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.
Apr
10
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.