A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.

learn more… | top users | synonyms

4
votes
2answers
232 views

Why does the modulus of Diffie–Hellman need to be a prime?

I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?
1
vote
0answers
22 views

Are the prime numbers used for RSA encryption known? [duplicate]

I read that one reason why RSA is secure is because it uses a huge number that's called the modulus which is the product of two prime numbers. For maths reasons the prime numbers being prime numbers ...
1
vote
4answers
105 views

Do any cryptography algorithms work on numbers besides primes?

I know prime numbers are important for several algorithms and protocols. Are there any algorithms and protocols that don't require primes?
-1
votes
0answers
43 views

Check if a number is Carmichael number efficiently

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number ...
0
votes
1answer
37 views

Security of Diffie Hellman in specific cyclic group

For some $k$, let's say $p = 1+ \prod_{j=1}^k q( j)$, where $q(1)=2$, $q(2)=3$, if $p$ is prime, the diffie-hellman key exchange is not secure in cyclic group $Z^*_p$. Why?
0
votes
0answers
16 views

Implications of pattern in finial digit of prime numbers [duplicate]

http://qz.com/639452/mathematicians-are-geeking-out-about-a-bizarre-discovery-in-prime-numbers/ What are the implications of this (very) new research on crytopgraphy? I would have thought this would ...
1
vote
0answers
72 views

“Prime conspiracy”'s effect on cryptography [duplicate]

Recent news reported about the discovery of a "Prime Conspiracy" which can be read about here. In summary, researchers have discovered that the last digit of prime numbers have a greater ...
3
votes
2answers
122 views

Why do we need Euler's totient function $\varphi(N)$ in RSA?

After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why? For decryption and encryption we only use $N$ and don't need $\varphi(N)$. So ...
1
vote
0answers
51 views

Fast algorithm for reduction modulo a prime [closed]

If the prime is $p=2^a\cdot3^b+1$ , is there any fast reduction technique modulo this prime?
3
votes
0answers
66 views

How common are weak RSA keys?

There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith. How common are these RSA keys? If you generate primes randomly, ...
2
votes
2answers
363 views

Sophie Germain primes and safe primes

I am trying to find a list or table of safe prime numbers i.e. the ones that are based on the Sophie Germain primes i.e. $N = 2p + 1$ where $p$ is also prime. All I found till now is this database. ...
0
votes
0answers
24 views

Is RSA safe anymore? [duplicate]

Some people may have heard of Shor's algorithm. It allows for integer factorization on a quantum computer. This wasn't a problem a little while ago since we didn't have any quantum computers. Google ...
2
votes
2answers
61 views

Obtaining Diffie-Hellman generator

In the Wikipedia article on Diffie-Hellman, the algorithm calls for a large prime modulus, $p$, and a generator, $g$, which is a primitive root of $p$. As far as my knowledge of number theory goes, ...
-1
votes
1answer
55 views

How much information is revealed?

Let Alice pick $v_{1}$,$m_{1}$$\in \mathbb{P}$ and Bob $v_{2}$,$m_{2}$$\in \mathbb{P}$. Now Alice computes $v_{1}$$^{m_{1}}$ and so Bob does $v_{2}$$^{m_{2}}$ Then Alice exchanges $v_{1}$$^{m_{1}}$ ...
3
votes
1answer
176 views

Difference between Pseudo Mersenne primes and Generalized Mersenne primes

The field prime numbers $p$ proposed by the NIST standards are referred to as Generalized Mersenne prime numbers [1] and as Pseudo Mersenne prime numbers [2]. Is there a difference between Pseudo ...
1
vote
0answers
26 views

Simple RSA Key Generation example [duplicate]

I have two prime numbers: p = 37 q = 41 And I need to find whether any of these prime numbers, 5, 7 or 11, can be used as a valid encryption key e? My working ...
20
votes
6answers
2k views

Is it feasible to build an index of prime factors?

Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
1
vote
1answer
111 views

How “hard” it is to take an e'th root mod p?

I know it's hard to find the $e$th root of a number mod $n=p_1*p_2$, and if it would be possible we could break RSA. But how hard it is to take an $e$th root mod $p$ where $p$ is a prime and ...
1
vote
0answers
17 views

RSA incorrectly translates for small keys [duplicate]

I've been learning about RSA and wrote my own implementation. I don't pretend to have intuitive understanding of RSA or that I understand why it works, but I believe to have some basic understanding ...
1
vote
1answer
160 views

Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$. (a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$. (b) Given the factorization of $N$ ...
2
votes
1answer
62 views

Largest number that could be factored in milli seconds

Considering a home pc/laptop as machine used (Say typical 2.4 GHz, 16GB RAM, 4 core processor) for running any factorization algorithm. What would be the largest number that could be factored into its ...
0
votes
2answers
131 views

Could Riemann hypothesis solve certainly RSA?

I don't have the background for dealing with Riemann hypothesis but is well known that covers the prime distribution below a specified number. In order to solve the RSA problem you have to factor the ...
2
votes
2answers
76 views

Find plaintext of RSA by solving extended euclidean algorith for two encrptions with two different exponents for same plaintext

This is my homework question (but I am not asking the answer to it): Suppose two users Alice and Bob have the same RSA modulus n and suppose that their encryption exponents eA and eB are ...
0
votes
1answer
56 views

Miller Rabin - Error probability of .5 a possibility?

I'm testing the property of Miller Rabin that the error probability is at most 1/4 when only a single base a is chosen and we iterate only one time. We are testing odd integers 90,000 to 100,000. ...
7
votes
3answers
10k views

What makes RSA secure by using prime numbers?

I am just learning about the RSA algorithm. Looking at the first two steps: Choose two distinct prime numbers $p$ and $q$. Compute $n = pq$. I have some probably stupid questions: Why do $p$ ...
36
votes
5answers
8k views

How are primes generated for RSA?

As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
5
votes
1answer
260 views

Why does Schnorr's Digital Signature scheme necessitate two prime numbers?

One of the necessary components to the Schnorr Digital Signature scheme is a pair of prime numbers $p$ and $q$ such that $q$ divides $p-1.$ However, there is never a modular inverse taken of q so why ...
6
votes
1answer
188 views

Why does GnuPG save an array of remainders when generating prime numbers?

In looking at GPG's gen_prime() function, found within the cyphers/primegen.c file of ...
2
votes
1answer
44 views

Requirements for the modulus in the Massey-Omura three pass protocol

In the Massey-Omura three pass protocol: How many bits long should the prime modulus $M$ be in order to be secure? Should the $M$ be secret? Should the $M$ be generated every time or it could be ...
4
votes
1answer
169 views

Cryptographic random numbers for key generation

I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are ...
14
votes
4answers
4k views

Is it possible to validate a Public Key in RSA?

If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)? (I suppose I am ...
1
vote
1answer
84 views

ssh-keygen DH Primality Testing

I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh. Reading over the man page, it says "By default, each ...
6
votes
1answer
157 views

What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$. Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is ...
0
votes
1answer
46 views

Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$

Given the natural number $n$, which is in the form $p^2 \cdot q^2$ with $p$,$q$ prime numbers. Also $\varphi(n)$ is given. Describe a fast algorithm (polynomial time) that calculates $p$ and $q$. ...
2
votes
1answer
601 views

Why should the primes used in RSA be distinct?

The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is ...
2
votes
1answer
96 views

Diffe-Helman Exchange result is always 1

I watched a video on Khan Academy explaining the Diffe-Hellman exchange. When I try to do an example problem, I get 1 all the time. Does the generator and prime modulus (or base on Wikipedia) have to ...
4
votes
1answer
217 views

Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain ...
-1
votes
1answer
330 views

Factoring large numbers

I am trying to factor few integers that are each between 115 and 135 digits long. I was wondering if anyone knew of any efficient methods or any programs that I could use to find the two primes $p$ ...
12
votes
1answer
548 views

RSA with probable primes

I am a bit of a newbie to RSA encryption, so please be patient. I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be ...
0
votes
0answers
85 views

What is the danger if a non-prime is chosen for RSA? [duplicate]

I was reading this question about generating primes for RSA keys. The answers point out that most implementations of of the algorithm use probabilistic prime-ness checking algorithms. The answer by ...
8
votes
3answers
3k views

Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526?

I was wondering if the prime numbers defined for use with Diffie-Hellman in RFC 3526 are more trustworthy than generating one's own, especially considering the recent Arjen Lenstra paper (Ron was ...
0
votes
0answers
72 views

Property of Multiplicative group of integers mod n

While practising on paper I've realized of a property of multiplicative group of integers mod $n$. First, let's define $G$ being $p$ a prime and $g$ a primitive root mod n or a generator of a ...
0
votes
1answer
108 views

Euler's Totient function for semiprime numbers

I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$ Let me explain myself by pointing to a brief example: ...
1
vote
1answer
166 views

Finding public exponent e

I'm trying to create an algorithm to find the public exponent e given a plain (non-CRT) private key that doesn't include the public exponent, i.e. I've only got $n$ and $d$. A question has already ...
1
vote
1answer
190 views

Why doesn't this defeat RSA?

Apologies for the obviously ridiculous question but I need to know where I'm going wrong here. For RSA, we compute $n=pq$ for primes $p$ and $q$. We then choose an $e$ such that $gcd(e, ...
0
votes
1answer
306 views

Timelock puzzle improvment

I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle ...
0
votes
1answer
79 views

If someone had a list of all primes, would it be possible for them to factor any integer in polynomial time? [duplicate]

For example, if they somehow got a function that would churn out any arbitrary amount of primes in a row. Could they break the RSA problem then?
2
votes
2answers
90 views

Is it hard to recover $p$ from $k \phi(p)$?

Given $k\phi(p)$, is it hard to recover $p$? Here, $p$ is a large prime, $\phi(\cdot)$ is Euler's totient function and $k$ is an unknown integer. Or what's the complexity to recover $p$ from $k ...
2
votes
2answers
3k views

phi(P*Q) = (P-1) * (Q-1)

I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$. However it seems that for a number $N$ such at $N=P\cdot Q$ where ...
0
votes
1answer
307 views