# 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.

293 questions
Filter by
Sorted by
Tagged with
2k 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 ...
3k 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 ...
151 views

### Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
637 views

### Is it possible to check if a number is the product of two primes without factorizing it?

I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox). I have started to run a factorization algorithm on it, and after a few hours ...
444 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 ...
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’...
2k views

### How to calculate y value from ((y*y) mod prime) efficiently

i am working ECC-224 bit. can any one tell me, how to calculate y value from ((y*y) mod prime) efficiently for large bit numbers.
319 views

### Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?

I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer ...
94 views

### Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
800 views

### Are there public $p$ and $q$ numbers for use in DSA?

There are many RFC documents giving large primes to use in Diffie-Hellman. However, I couldn't find standards on the $p$ and $q$ large primes used in the DSA signature scheme. This is proving to be a ...
1k views

### RSA primes vs. largest known primes

In the context of a new largest (mersenne) prime number being found this week - The largest known prime number is now 2^57,885,161 − 1, and it took 5 years to find ...
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 ...
124 views

### Magic Number to calculate number of rounds for M-R in FIPS 186-4

In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases. Does anybody ...
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 ...
1k views

### How big are the primes used in modern cryptography?

I know that this depends on which techniques you're using, but roughly speaking, when modern cryptography makes use of so-called "large prime numbers", how large (in bits or digits) are these primes ...
2k views

### For Diffie-Hellman key exchange method, what are examples of very poor a and b values?

For Diffie-Hellman key exchange method, what are examples of very poor $a$ and $b$ values? Given that $g$ and $p$ values are both large prime number and the formula is $$g^{a . b} \bmod p$$
2k views

### Issue implementing Pollard's Rho for discrete logarithms

I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to ...
270 views

### Nothing Up My Sleeve Lim-Lee Primes

A few days ago I asked a question about the security of the Lim-Lee Prime Generation algorithm used by GNU Privacy Guard’s libgcrypt library. L. Carvalho provided a good answer to that question. ...
2k views

### Visualization of cryptography

I think CrypTool is great software. And what I find most useful in it is visualization of algorithms such as Caesar, Vigenere, AES, DES. And my question is: does anyone know other tools which are ...
79 views

### Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run ...
167 views

### Malicious DH parameters without using composite numbers [duplicate]

I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
2k 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, ...
822 views

### RFC 3526 - What does pi mean?

In RFC 3526 there are a series of primes listed as standard parameters used for Diffie-Helman. The primes are list in two formats. One is the long format, where the number is given in hex. For example:...
92 views

### Consequence of $p\bmod e=2$ in RSA prime generation

When generating a prime $p$ for use in an RSA modulus with public exponent $e$, it is necessary that $\gcd(p-1,e)=1$. When $e=3$, and since $p$ is a large prime, that implies $p\bmod e=2$. Assume an ...
1k views

### Probability that n is prime such that n fails the Miller-Rabin test N times

I'm working through An Introduction to Mathematical Cryptography and one of the exercises asks Suppose that we run the Miller–Rabin test N times on the integer n and that it fails to prove that n ...
527 views

### Probability of Fermat test going wrong

How can I proof that in Fermat's primality test the probability of going wrong after k iterations is $\big(\frac{\phi(n)}{n-1}\big)^{k}$?
629 views

### How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$

Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form? This is actually a homework problem with a ...
677 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 ...
99 views

### Source of very large prime numbers

The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers. With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ ...
50 views

### Generalized Benaloh cryptosystem with $r=2$

Benaloh cryptosystem requires $\gcd(r, (q-1))=1$ which is impossible if $q>2$ (since it needs to be a large prime) and $r=2$. This confuses me, since Benaloh is referred to as an "extension" or "...
229 views

### Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
2k views

### Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
878 views

### ABC Conjecture's Impact on RSA Encryption

A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
206 views

### Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.) I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows. I ...
544 views

### Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?
925 views

### Large prime numbers in encryption?

I have recently been reading about encryption and the importance of prime numbers and I have some questions that I would really appreciate some answers to, if possible: Is it correct that when ...
3k 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?
260 views

### Diffie-Hellman in Https: How are prime numbers picked?

I am trying to understand https, as I understand https uses the Diffie–Hellman method for keys exchange and then AES for encryption. But Diffie–Hellman needs two prime numbers, where do these come ...
90 views

### Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
584 views

### Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
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. ...
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.
293 views

### Why are huge prime numbers important in cryptography?

I read an article the other day about the search for prime numbers. According to the article and several online sources the biggest prime number is over 17 million digits! This made me wonder why ...
532 views

### Are relatively prime numbers used in RSA

We know that the Totient function is multiplicative. Which means that when $p$ and $q$ are relatively prime, then $\varphi(p q)$ is equal to $\varphi(p) \varphi(q)$. My question is, are only prime ...
930 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  and as Pseudo Mersenne prime numbers . Is there a difference between Pseudo ...
224 views

### RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked. what is the advantage in factoring $N$? Does this give an advantage beyond simply lowering the number of bits we ...
222 views

### Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

My company wants to generate new primes for every Diffie-Hellman key exchange. We are thinking of using the prime generation scheme in GPG’s libgcrypt library. The code documentation says that the ...
853 views

### RSA - twin primes, two modulus

I'm working on this problem. I'm given \begin{align*} n_1 &=pq\\ n_2 &=(p+2)(q+2) \end{align*} where $p$ and $q$ are twin primes, i.e. $p$ is prime and $p+2$ is also prime; similar for $q$...
I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, ...