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
3
votes
1answer
219 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 ...
2
votes
1answer
445 views

Diffie Hellman unsafe prime vulnerability

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor ...
1
vote
1answer
456 views

Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses?

Factoring a 2048 bit number is a difficult topic with a well known complexity. But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the ...
1
vote
0answers
616 views

See the RSA's $n = p q, e \text{ and } d$ from ssh-keygen

For learning purposes, how to get the RSA's parameters (I use standard notation): $n = p q $, where $p$ and $q$ are prime and $e$, $d$, such that $ed = 1 \ (mod\ \varphi (n)) $ when doing ...
1
vote
0answers
86 views

Probability of a prime factor [closed]

We are given an arbitrary number $n$ and a sequence of primes $p_1=2$, $p_2=3$, ..., $p_k$. I am interested in the following question: Are the events "Prime $p_i$ is a factor of $n$" independent for ...
2
votes
1answer
157 views

For large prime P, how often is (P-1) evenly divisible by 65537?

When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537). I'm curious ...
-2
votes
1answer
139 views

are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...
2
votes
1answer
1k views

How to encrypt the number one using RSA?

for example: if we have public key : (5,221) and private key : (77,221) and we want to encrypt 1: c(m) = (m)^p mod n c(m)=(1)^77 mod 21 =1 so how to deal with ...
0
votes
1answer
2k views

What algorithm does .NET use to generate primes for RSA and how can I verify it?

There is an implementation of RSA in C# .net, but how can people know that this implementation is considering all the secury stuff conserning to RSA? For example I want to know what is the algorithm ...
0
votes
1answer
912 views

What are some of the best prime factorization algorithms and their effecitvity

I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem? The way it looks to me is that every time an algorithm is able to ...
0
votes
1answer
2k views

How to Check Strength of RSA Public Private Key

How to measure strength of RSA public private key pair. is it enough to only measure the length of primes used to generate N? how to check that primes p,q used to make N were selected truly randomly ...
11
votes
1answer
191 views

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?
0
votes
1answer
112 views

Factorizing a handiwork number $n$ in two prime factors

I have generated two primes $r_0$ and $s_0$ with same bit size $\le 64$, then make another two primes as follows: choose constant $k$ and define $$r_i = r_0 + \alpha_i, \quad 1 \le i \le k, \quad 0 \...
1
vote
1answer
136 views

Do we always use Sophie-Germain primes $1\bmod 4$?

A prime $p$ is Sophie Germain if $2p+1$ is also prime. Wiki says if $p\equiv3\bmod4$ then $2p+1|2^p-1$. This seems to put a huge restriction on density of Sophie-Germain prime if they are $3\bmod4$. ...
2
votes
1answer
301 views

RSA: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$

Say we have chosen $n=pq$, with $p=89,q=97 \implies n=8633$ and $\varphi(n)=88\times96=8448$. Also, if we want the encoding ($e$) and decoding ($d$) exponents to be equal, we need $$(e,8448)=1 \: \: \...
1
vote
1answer
886 views

Find inverse in RSA

I've been reading on RSA for a while but there's something I still can't understand. When generating the key: once you find n = pq and φ(n), you choose a number d coprime with φ(n) and then you need ...
2
votes
1answer
1k views

Mathematics behind end-to-end encryption

I am interested in end to end encryption, recently I read some articles on its principles but I can't find anything on the maths behind the encrypting and decrypting functions that relates private and ...
0
votes
2answers
256 views

Can someone explain the definition of four square roots as it pertains to groups in Z*p?

So I'm given the following as a problem: When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square ...
2
votes
1answer
333 views

where does the prime number taken in DH algorithm in IPSEC

I am studying & configuring IPSEC ikev1 and in between i am analysing the wireshark captures. I am using the linux kernel for TCP/IP stack and user-space i took ipsec-tools. In the first two ...
3
votes
2answers
542 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)?
9
votes
2answers
2k views

Why are elliptic curves constructed using prime fields and not composite fields?

I come across this: Numbers mod composite number does not form a field rather it forms a ring and every number has a multiplicative inverse under integer mod prime Maybe these are the reasons ...
1
vote
1answer
384 views

Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
-1
votes
1answer
100 views

Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.
0
votes
2answers
124 views

complexity of iterative squaring in relation to factorization

I've run into a question dealing with the number of modular multiplications of O(n) bit numbers in the following situation: Given two n bit primes p,q define m=pq. ​ ​ ​ Choose some 'a' so that ​ $2&...
2
votes
1answer
1k views

Why are cube and square roots of primes used as SHA constants?

Do square or cube roots have properties that make them a better choice over, for example, the primes themselves? Or is it arbitrary - would random numbers work as effectively?
1
vote
1answer
204 views

Primality test in GPG/RSA or extract numbers of private key

I cannot find if the two numbers for RSA are tested against an elliptic curve primality test. If not, is there a way to extract the two integers of my private key in order to test it by myself? If ...
0
votes
0answers
68 views

Finding two primes that satisfy the conditions

I want to implement partially blind signature, and I looked at Zheng Gong's scheme. (Title: Efficient Partially Blind Signature Scheme with Provable Security) In the scheme, there is a initialization ...
4
votes
1answer
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 ...
1
vote
1answer
3k views

How many p and q pairs are there in a 1024 bit modulus?

I was reading: Is sharing the modulus for multiple RSA key pairs secure?. My question is: Given a 1024 bit modulus, how many pairs of 512 bit p's and q's are there that would be able to be ...
1
vote
2answers
218 views

Can we (with just paper and math) find the prime number “p” of an RSA key?

With all our tools in math, isn't it really possible to find the prime number p of an RSA key without brute-forcing it with a computer? I'm not talking about doing it in 2 minutes but doing it in a ...
4
votes
1answer
525 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}$?
4
votes
5answers
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$$
4
votes
2answers
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 ...
3
votes
1answer
910 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 ...
3
votes
1answer
844 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$...
-2
votes
1answer
296 views

RSA and Prime numbers distribution law [duplicate]

I have read a few articles and watched some Youtube videos explaining the algorithm of RSA. It seems that RSA is mainly based on a mathematical trick (Prime Factorization). I am wondering though what'...
2
votes
2answers
3k views

The problem of 'Common DH Primes'

NSA crack multiple encrypted channel by some tricks on 'Common DH Primes', which is a old news, but how actually they crack it? I still can't get the concept why using a 'Common DH Primes' will ...
1
vote
0answers
85 views

Algorithms to test vs. generate primes

What would be the value in having a true prime number generator algorithm instead of a prime number test algorithm? Also, if such a thing existed, what would be the impact on not only cryptography?
3
votes
1answer
228 views

Why does FIPS 186-4 seem to have an excessively complex q generation?

So in DSA you have two primes - p and q. q is N bits long (let's assume 160 bits) and p is L bits long (let's assume 1024 bits). Here's what FIPS 186-4 says about generating the q parameter for DSA: ...
0
votes
1answer
115 views

factorization of an integer $N$ that is in special format

Suppose $p_0$ and $q_0$ are known prime numbers and define $p_i$ and $q_i$ as follows: $$p_{i+1} = next\_prime(p_i^2 + q_i^2), \qquad i \ge 0$$ and $$q_{i+1} = next\_prime(2p_iq_i), \qquad i \ge 0$$ ...
1
vote
0answers
549 views

How to generate 1000 prime number of 1024-bit with much less time?

I am generating thousand prime number of 1024 bit each. But it takes lots of time. My procedure is as follows. Generate prime number using ...
2
votes
1answer
159 views

Highest prime factor that is Safe for a particular scheme

My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number? Quantum computing find ...
2
votes
1answer
617 views

Sieving the sequence $x^2-n$ to recognize b-smooth numbers

I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question: [1] An Introduction to Mathemtaical Cryptography by J. ...
25
votes
6answers
21k views

Why does RSA need p and q to be prime numbers?

Despite having read What makes RSA secure by using prime numbers?, I seek a clarification because I am still struggling to really grasp the underlying concepts of RSA. Specifically, why can't we ...
1
vote
1answer
113 views

New Improved Probabilistic version of RSA

On the 2nd page of "New probabilistic public-key encryption based on the RSA cryptosystem" by Roman'kov (PDF), at last it says Alice can find "f" of order "l" with least probability of (1-1/l). I ...
6
votes
2answers
657 views

How to test implementation of primality tests like Miller–Rabin?

The Miller-Rabin primality test is an algorithm for checking if number is a prime. What would be best way to test implementation of such algorithm (or any primality test in general)?
15
votes
2answers
2k views

NIST Diffie-Hellman prime: how was it picked? Where did it come from?

According to this Matasano Crypto challenge, the NIST "likes" the following prime modulus, which appears to be expressed in hexadecimal: ...
2
votes
0answers
44 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
1answer
278 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?
1
vote
0answers
85 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 ...