Questions tagged [prime-numbers]

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.

Filter by
Sorted by
Tagged with
2
votes
2answers
639 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 relatively ...
0
votes
1answer
891 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. I'...
7
votes
3answers
5k 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?
7
votes
1answer
209 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 ...
4
votes
1answer
657 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 ...
1
vote
1answer
389 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 ...
0
votes
1answer
60 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$. ...
6
votes
1answer
281 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 ...
2
votes
1answer
142 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
2k 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
137 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 ...
0
votes
0answers
375 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 @...
0
votes
0answers
261 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
600 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: $...
3
votes
1answer
2k 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 ...
23
votes
1answer
4k 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 ...
1
vote
1answer
362 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, \varphi(n))=1$...
1
vote
1answer
112 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
267 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 \phi(...
2
votes
1answer
1k views

RSA modulus (N) from public key and calculating N from p, q not equal [closed]

I have a RSA public key in the form of public exponent and modulus as follows: ...
1
vote
1answer
2k views

Creating a random password based off of a prime number

So I am making an application that basically creates strings that must be encrypted before they are stored on a user's device. If the user blindly starts running the application without creating a ...
0
votes
1answer
224 views

Of what use is my code for finding prime numbers of a certain size? [closed]

I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
-3
votes
2answers
201 views

Why would cryptography fall apart if there were a finite number of primes? [closed]

I vaguely know that prime numbers are very important in cryptography, but I assume for most encryption methods, they tend to stay rather 'small'. Are we really using massive prime numbers for ...
0
votes
1answer
713 views

Prime modulus for RSA and sharing a secret?

According to this paper entitled "Using Commutative Encryption to Share a Secret" they define their modulus to be a large prime p, which is public. Both exponents are private in this case. According ...
0
votes
1answer
239 views

Proof that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$

What is the proof for the fact that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$ Where: $N = P * Q$ where $P$ and $Q$ are both primes. $\varphi(N)$ ...
1
vote
1answer
368 views

Why is factoring $p-1$ easy when $p$ is a safe prime?

A paper states: [...] $(p,g,y)$ is a correct ElGamal public key if $g^x=y\pmod p$. To verify this the order of $g$, and thus the factorization of $p-1$, is needed. This is easy for safe primes (i.e....
5
votes
3answers
2k views

Finding strong primes

Wikipedia lists the following conditions for a prime to be strong: $p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$. $q_1-1$ has large prime ...
2
votes
2answers
1k views

Factors of RSA modulus

In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
0
votes
1answer
238 views

How much (home PC) CPU time is required to generate a prime number of a given size?

How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes? Please note that ...
3
votes
2answers
2k 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
1answer
155 views

Prime Numbers in Discrete Log

I am implementing a security protocol based on discrete log. I came across the equation $p = kq + 1$. Understand that based on number theories that both $p$ and $q$ should be large enough to be "safe"....
3
votes
2answers
2k views

Significance of 3mod4 in squares and square roots mod n?

Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?
25
votes
5answers
20k views

Why are primes important for encryption

Why are primes so important? Why can't we just use a random number? My guess is that it's because finding a random prime require more computing power, than finding a random number. Can anybody confirm ...
1
vote
1answer
180 views

Fermats Little Theorem, primitive root [closed]

So I am studying for finals and I am not able to solve the problem: Let $ p = 3 * 2^{11484018}- 1 $ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x\equiv 3\pmod p$ Any ...
0
votes
1answer
524 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 ...
5
votes
2answers
1k views

Generation of strong primes

It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes $p$ where $(p-1)$ has a very large prime factor. Is there any information regarding the ...
4
votes
2answers
2k views

Is there a way to systematically calculate the public exponent $e$ in RSA?

I'm learning RSA in one of my classes and we were given a problem: $p = 5$, $q = 11$ I have done the following steps: $n = 5 \cdot 11 = 55$ $\phi = (5-1)\cdot(11-1) = 40$ I know that to find ...
1
vote
1answer
93 views

special public keys and modulo n

I just picked up cryptography and have some questions on RSA cryptosystem: Say there are two public keys (n, e1), (n, e2), e1 is coprime to e2. They share the same n. Is it possible to find the ...
1
vote
1answer
527 views

In RSA, why does Alice's $N$ need to be relatively prime to Bob's $N$?

I was asked this by my professor and I didn't understand the reasoning behind it. If Alice has a the key pair $(p_a, n_a)$ and Bob has the key pair $(p_b, n_b)$, why do $n_a$ and $n_b$ have to be ...
3
votes
1answer
218 views

NIST implementation of the Lucas primality test

The NIST standard FIPS 186-4 describes an implementation of the Lucas primality test in section C.3.3. I can follow the algorithm but I am puzzled by step 6.2: $V_{temp}=\frac{V_{i+1}^2+DU_{i+1}^2}{...
10
votes
4answers
4k views

What is the use of Mersenne Primes in cryptography

There is an international search for Mersenne Primes. The project is huge. But what is the use of Mersenne Primes in cryptography? Do they have any other properties other than the $2^n-1$ form?
6
votes
2answers
2k views

Small Prime Difference in RSA

In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small. Suppose that $u=|p-q|<20$ and $p \times q =...
1
vote
1answer
605 views

Compare two approaches for cracking RSA key

I came across these questions while studying for a crypto course, does anyone have any ideas on how to answer these? (a) Random prime numbers of size 1536 bits are chosen to generate an RSA modulus ...
3
votes
1answer
2k views

How can convert affine to Jacobian coordinates?

I have a point in affine coordinates: $(x,y)$. What should I do when I want to convert to $(X,Y,Z)$ in Jacobian coordinates? I need it for calculating ECC in a prime field.
1
vote
1answer
379 views

How costly is to find millions of large prime numbers for RSA?

Consider I need to assign a large distinct prime number to each element in a large set. This must be deterministic so the function always gives me the same prime to the same value. What is the most ...
3
votes
1answer
2k views

Generation of N bit prime numbers -> what is the actual range?

Short version: When generating a prime number of N bits, should I draw random numbers from the range $[0 , 2^n]$, or $[2^{(n-1)} , 2^n]$? Context: I'm trying to implement a toy-version of RSA as a ...
1
vote
1answer
127 views

How can i calculate prime of Elliptic Curve?

In many articles i have found directly the calculation of prime elliptic curve. How can i calculate this prime $p$ ? For example if I consider NIST P-256, $ p = 2^{256}-2^{224}+2^{192}+2^{96}-1$. Why ?...
1
vote
1answer
388 views

Equal length of primes in paillier cryptosystem

In the key generation step of paillier cryptosystem , In order to satisfy $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes. Instead of taking(length as parameter to generate $p,q$) equal ...
1
vote
1answer
484 views

Choosing primes in the Paillier cryptosystem

In the first step of key generation phase in Paillier cryptosystem given here. It's given that $$\operatorname{length}(p) = \operatorname{length}(q) ) \implies \operatorname{gcd}(pq,(p-1)(q-1))=1$$ ...
5
votes
1answer
4k views

RSA example-calculation: Public Key = Private Key (e = d)

I am a bit confused. I just calculated manually the single steps of RSA for an implementation with small numbers and suddenly $d$ was equal $e$. Please help me understand what I am doing wrong. Here’...