Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
57 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
0answers
29 views

How to Generate an Instance of Discrete Logarithm Problem [duplicate]

I am looking to generate an instance of the discrete logarithm problem in Java, using a cyclic field $F_p$ with its generator $g$. But looking for a generator of a field could take too long, So is ...
-1
votes
1answer
95 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
142 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
54 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 ...
3
votes
1answer
96 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
108 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
69 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 ...
1
vote
1answer
104 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 ...
0
votes
0answers
14 views
14
votes
2answers
473 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
209 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
171 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
52 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 ...
0
votes
0answers
117 views

Rsa factoring best method and time

I am going to participate in a local challenge where you have to guess the two prime numbers(p and q), they give you a 8 bits number, 16 bits number..., 128 bits number... , 512,1024,2048... and wins ...
-1
votes
2answers
155 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
102 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
131 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, ...
0
votes
0answers
167 views

Generating a safe prime and its primitive root

I am trying to write a program for Verifiable Secret Sharing, where I want to generate large prime (512 bit) and to find its primitive root. Giving such a large prime, I have to generate a safe ...
2
votes
1answer
52 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
242 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
39 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
378 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
81 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 ...
0
votes
1answer
270 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
116 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 ...
2
votes
1answer
78 views

Malicious DH parameters without using composite numbers

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
88 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
109 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
69 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
129 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
63 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
199 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
75 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
129 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 ...
0
votes
0answers
36 views

Why for a secure RSA the difference of | p - q | should not be too small? [duplicate]

I am pretty new in this cryptography world and I have some doubts. Please help! So, for a secure RSA modulus $n=pq$ , this difference $( |p-q| )$ should not be small, then if we choose an integer, ...
3
votes
1answer
193 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
204 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
147 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
73 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
114 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
88 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 ...
3
votes
1answer
887 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 ...
-1
votes
1answer
800 views

What algorithm use .net 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
382 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
1k 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
166 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
69 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
89 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$. ...