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
487 views

Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
0
votes
0answers
81 views

Yukel's Sieve - Factorization of Numbers into a Square Sieve

https://www.youtube.com/watch?v=liTTGeitpGQ https://www.youtube.com/watch?v=2nOwgiweyqc https://www.youtube.com/watch?v=rGwFsOG27DQ I came across these videos explaining a pattern that is found in ...
6
votes
1answer
166 views

Distinguishing generators of RSA primes and moduli

We are trying to distinguish two RSA prime generators: Prime generator 1 draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$, until it is prime output $p$. Prime generator 2 ...
3
votes
2answers
448 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 ...
5
votes
1answer
2k views

How does Python's pycrypto library generate primes?

The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows: from Crypto.Util import number number.getPrime(2048) The ...
4
votes
1answer
118 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 ...
1
vote
0answers
43 views

Random Primes Conjecture [closed]

I know it is believed that primes appear to be randomly distributed among the integers. Is there a formal conjecture or theorem that expressly states that the occurrence of the prime numbers is ...
1
vote
1answer
115 views

How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
7
votes
2answers
2k views

How to efficiently generate a random safe prime of given length?

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 ...
2
votes
1answer
302 views

DSA: How to calculate 224-bit $q$ for 2048-bit $p$

$p$ is a 2048 bit prime number $q$ is a 224 bit prime number I know that $q$ is a prime divisor of $p-1$, thus $p=1 \bmod q$ but I couldn't write efficient code to calculate this. I can calculate ...
1
vote
1answer
63 views

How to formally say that the integers modulo $p$ for a prime $p$ gives results that are “more random” than for a composite $n$?

I'm doing a presentation on cryptography for non-experts. My main algorithm of the presentation is the Diffie Hellman key exchange. It uses modulo arithmetic for a prime $p$. During my presentation, I'...
-1
votes
1answer
230 views

Swift and (very) large integers [closed]

I am trying to write a simple Mac program to factor primes. Nothing new, but I have a problem. The largest integer I can use seems to be 2^64, which is not that big. Did you hit any similar problem? ...
1
vote
1answer
694 views

RSA finding p and q integer with condition

I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447). In ...
-1
votes
1answer
73 views

What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
4
votes
1answer
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 ...
1
vote
2answers
583 views

In RSA, is it possible to compute the private key if one knows one of the primes used to generate n?

Within RSA the private key can be derived if one knows both $p$ and $q$. Is it possible to derive the RSA private key or decrypt / learn something about encrypted messages if you only know one of the ...
3
votes
3answers
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 ...
0
votes
2answers
89 views

Public-key generation - primes reuse

Given the following Trap-door Commitment scheme Secret key receiver: $x_B \in_u Z_q$ Public key receiver: $y_B = g^{x_B} \mod p$ Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the ...
3
votes
1answer
346 views

Efficient algorithm for finding Sophie Germain primes

What's the industry standard for an efficient finding large Sophie Germain primes? As a part of request handling in my application, I need to generate Paillier key. My current approach is to ...
16
votes
2answers
1k views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
4
votes
0answers
228 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 ...
-1
votes
1answer
183 views

Does Parallax Compression endanger cryptography?

http://www.novaspivack.com/science/we-have-discovered-a-new-pattern-in-the-prime-numbers-parallax-compression A lot of cryptographic algorithms depends on prime numbers. Will this influence any ...
4
votes
1answer
78 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 ...
-1
votes
2answers
172 views

A quick way to justify whether $a^m \equiv 1 \pmod{n}$?

Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
0
votes
2answers
173 views

Why is prime factorisation computationally intensive compared to normal factorisation?

Why do we use prime factors in asymmetric algorithms compared to other factors? For example: lets say we use two prime numbers p = 53 and q = 59 our public key in RSA algorithm would be p * q =...
1
vote
1answer
390 views

Example of calculating a primitive root for large prime?

I am trying to figure out how to calculate primitive root $w$ for a prime. Following what I read, I generated my prime to be 'safe prime', $p=qr+1$. I know $q$ (also prime) and $r$. Let's assume, ...
2
votes
1answer
70 views

Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment: (You might want to keep the certificate secret too.) As the ...
0
votes
4answers
405 views

Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$

Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime. A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
0
votes
1answer
42 views

Breaking a modified version of Diffie Hellmann Protocol

I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt ...
1
vote
1answer
937 views

How to find the public key in RSA?

Finding the public key given the private key $d$ and the prime numbers $p$ and $q$. $$p = 3092551601$$ $$q = 3490383433$$ $$d = 10719928016004921607$$ Since this is RSA, here is my thinking. In ...
-1
votes
2answers
83 views

Understanding reversible addition in a prime field

I'm trying to understand the security implications of addition in a prime field. Suppose I have X + Y = Z, occurring under prime field P(W) where W is the size of the field. If I know X and Z, I ...
1
vote
1answer
1k views

primitive root of a very big prime number (Elgamal DS)

For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime ...
3
votes
1answer
157 views

Biased RSA moduli and ROCA

Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences ...
4
votes
1answer
151 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 ...
5
votes
1answer
93 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 ...
-1
votes
1answer
148 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
0
votes
1answer
101 views

generating prime p and q, with alpha of element of order q

I'm working on VSSS (Feldman) but I cannot understand the statement as follows: I'm not good in reading mathematical statements (but working on it). Can anyone explain this in simple mathematics. ...
1
vote
1answer
184 views

Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
2
votes
1answer
78 views

AugPake implementation Doubt K computation

try to implement the AugPake protocol in java using BigInteger. I am having some difficulty computing $K=Y^z \mod p$ because $z$ is always $0$, for $z={1\over x+(w*...
4
votes
2answers
257 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. ...
-3
votes
1answer
89 views

Are there stenography benefits to a “n-prime”?

As mentioned in this StackOverflow CodeGolf question, prime numbers can be redefined: One of my favorite definitions of the prime numbers goes as follows: 2 is the smallest prime. ...
3
votes
1answer
205 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
417 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
444 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
577 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
85 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
151 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
136 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 ...