All Questions
Tagged with cryptography prime-numbers
118
questions
0
votes
1
answer
64
views
Is there an algorithm that uses prime numbers in symmetric encryption? [closed]
It is well known that there are algorithms developed for asymmetric encryption that take advantage of the fact that the product of two prime numbers cannot be factored in polynomial time. Usually, ...
0
votes
0
answers
50
views
Finding an algorithm to factor $n$ given cube root $\mod n$
Let $p,q$ be unknown primes and $n=pq$.
Also let:
$p\equiv 4 \mod 9$
$q\equiv 4 \mod 9$
Imagine I have an "oracle" that takes cube roots $\mod n$. Find a probabilistic algorithm to factor $n$...
2
votes
0
answers
50
views
The number of integers less than x that have at least two distinct prime factors of bit size greater than one-third the bit size of x
Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, ...
- 123
1
vote
3
answers
129
views
Why are there always two primes between $2^n$ and $2^{n+1}$?
In a cryptographic lecture we just assumed that this statement holds. In particular, we said for a fixed length of bits one can always find two primes, that have the same length in binary ...
- 157
0
votes
0
answers
81
views
How difficult this RSA cracking algorithm is.
If the way to crack the RSA algorithm is knowing the factors of a number. How easy can the factors be obtained by taking the reverse 'long product'?.
For instance, if you have the product of three ...
0
votes
0
answers
63
views
Factor equation?
For semi-prime c, is there an equation or system of equations that will find its factors?
In other words, if a prime number a ...
1
vote
1
answer
320
views
Finding one of the two prime factors in RSA from the above equations, if we know what the c1,c2,e1,e1,N are.
There is a problem i am trying to solve on RSA.
We have two ciphertexts which have been encrypted with different public exponents e, but share the same modulus N.
Assume that the c1,c2,e1,e2,N are ...
- 13
0
votes
1
answer
48
views
I am trying to understand whether this equation has a solution using either Legendre's or Jacobi's symbols [duplicate]
The equation in question is x*x≡1097 (mod 65539).
The online calculators and sagemath have said there are no solutions but I can work it out on paper using the Legendre properties.
How come sagemath ...
- 1
0
votes
0
answers
78
views
Likelihood of 2 being a liar in Miller Rabin test for large number (e.g. 1000+ bits)
I have written some working code to generate RSA key pairs using the Miller-Rabin primality test. All of the generated keys pass the openssl rsa -check function, meaning that (among other things) ...
0
votes
0
answers
190
views
Prime and co-prime numbers importance in Cryptography
I am currently writing a math paper for school regarding RSA encryption my focus lies on the importance of prime and co-prime numbers within the algorithm.
I understand that this is a "trap-door&...
1
vote
0
answers
204
views
Understanding the ramifications of Riemann Hypothesis
Proving Riemann Hypothesis is a million dollar problem, but I am more interested in understanding its ramifications in the practical world.
According to many sources, one such effect will be ...
- 395
1
vote
0
answers
113
views
RSA Problem : Encrypt the letter J in ASCII (decimal) with public key RSA (n=147, e=7) ...
Encrypt the letter J in ASCII (decimal) with public key RSA (n=147, e=7), then compute the private key and decrypt the result confirming that the message has been sent.
First part
J = 74 (ASCII), $n =...
- 69
1
vote
1
answer
126
views
Prove that any element $g\in(\mathbb{Z}/n^2\mathbb{Z})^\times$ of order $n$ can be written as $g = 1 + kn$ with $\gcd(k,n) = 1$.
Let $p$ and $q$ be two primes such that $p \nmid q-1 $ and $ q \nmid p-1$ (note that these two hypotheses could be superflous, but this is the context given by Paillier cryptosystem) and let $n = pq$. ...
- 33
0
votes
1
answer
37
views
Factoring $pq$ if $x \equiv y \mod p$ and $x \not\equiv y \mod pq$
Let $G = \mathbb{Z_N}$ be a finite cylcic group of order N = $pq$ . The generic Pollard's Rho algorithm searches for 2 elements $x,y \in G$, such that $x \equiv y \mod p$ and $x \not\equiv y \mod pq$ ....
1
vote
0
answers
43
views
Probabilistic primality test that might return a prime as a composite but never a composite as prime
I am currently analyzing the AKS algorithm and I saw that for practical purpose usually only probabilistic test are used due to faster runtime. I know that the probabilities in these test can be made ...
- 41