Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
137
questions
9
votes
2
answers
2k
views
$a^{\phi (n) +1} \equiv a \pmod{\! n}; $ Carmichael generalization of Fermat & Euler theorems.
I want to know a proof of an alternative form of Fermat-Euler's theorem
$$a^{\phi (n) +1} \equiv a \pmod n$$
I searched some number theory books and a cryptography book and internet, but there were ...
- 652
120
votes
5
answers
181k
views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
user27617
4
votes
1
answer
477
views
How to compute $k$'th roots $\!\bmod m$?
I have the following equation:
$$
n \equiv M^k\pmod b
$$
where $n, k, b$ are integers, and $M$ is an unknown integer. How can I solve this equation to find $M$? Here $k$ and $b$ are public keys of the ...
- 5,411
3
votes
2
answers
2k
views
Solving the congruence $x^2 \equiv 4 \mod 105$. Is there an alternative to using Chinese Remainder Theorem multiple times?
I'm trying to solve $$x^2 \equiv 4 \mod 105.$$
This is of course equivalent to $$(x+2)(x-2) \equiv 0 \mod 105$$
which is also equivalent to the system of congruences
$$(x+2)(x-2) \equiv 0 \mod 3$$
$...
- 1,862
-1
votes
3
answers
169
views
Why does $(g^b \bmod m)^a \bmod m = (g^a \bmod m)^b \bmod m$?
I have been trying to understand why the Diffie Dellman key exchange algorithm works, specifically why the two exponents can be swapped in it without the result changing.
So my specific question is ...
42
votes
2
answers
28k
views
Why are very large prime numbers important in cryptography?
Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others.
Secondly, a friend asked me recently why large primes are important for data security, and I was ...
- 1,757
18
votes
3
answers
11k
views
RSA: How Euler's Theorem is used?
I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part.
I'm assuming
$$n = pq$$
$$m = \phi(n) = (p - 1)(q - 1)$$
E is the encryption key $\gcd(\phi(n), ...
- 733
6
votes
2
answers
13k
views
RSA: Fast factorization of N if d and e are known
I stumbled across this paragraph in a paper:
Hence, user b cannot decrypt C
directly. But using e and d , user b
can quickly factor N.
How is it possible to speedup the prime factorization ...
- 205
1
vote
2
answers
6k
views
Extended Euclidean Algorithm in $GF(2^8)$?
I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended ...
- 125
10
votes
2
answers
10k
views
Is the set of all finite sequences of letters of Latin alphabet countable/uncountable? How to prove either?
Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can ...
- 5,296
9
votes
4
answers
11k
views
Practical method of calculating primitive roots modulo a prime
How are generators of a (large prime) set calculated in popular programs such as pgp and libraries such as java's bouncycastle? i cannot imagine them just churning away at every value between 2 and p ...
- 235
2
votes
5
answers
1k
views
Solving the congruence $7x + 3 = 1 \mod 31$?
I am having a problem when the LHS has an addition function; if the question is just a multiple of $x$ it's fine.
But when I have questions like $3x+3$ or $4x+7$, I don't seem to get the right answer ...
5
votes
1
answer
8k
views
Use Pohlig-Hellman to solve discrete log
We have $$7^x = 166 \pmod{433}$$
I need to find $x$ using the Pohlig-Hellman algorithm.
- 131
60
votes
4
answers
16k
views
Would a proof to the Riemann Hypothesis affect security?
If a solution was found to the Riemann Hypothesis, would it have any effect on the security of things such as RSA protection? Would it make cracking large numbers easier?
- 5,459
31
votes
2
answers
12k
views
Proving the Riemann Hypothesis and Impact on Cryptography
I was talking with a friend last night, and she raised the topic of the Clay Millennium Prize problems. I mentioned that my "favorite" problem is the Riemann Hypothesis; I explained what it posits ...
- 17.8k