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.

learn more… | top users | synonyms

2
votes
1answer
306 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
101 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 ...
16
votes
5answers
3k 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
2answers
337 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?
1
vote
1answer
84 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
0answers
149 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 ...
2
votes
2answers
310 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 ...
0
votes
1answer
63 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 ...
3
votes
2answers
334 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 ...
12
votes
3answers
7k views

How does one calculate a primitive root for Diffie-Hellman?

In the Diffie-Hellman key exchange, one of the steps involves calculating a primitive root of a prime number $p$. How would one go about doing so, considering that $p$ could be very large? Is there ...
3
votes
1answer
94 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: ...
0
votes
1answer
107 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 ...
1
vote
1answer
197 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
230 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.
6
votes
3answers
1k 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?
1
vote
1answer
268 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 ...
7
votes
2answers
1k views

How to better generate large primes: sieving and then random picking or random picking and then checking?

I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q). I know of two methods to achieve this, one based on a prime number ...
1
vote
1answer
284 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 ...
4
votes
1answer
2k 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. ...
2
votes
1answer
381 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 ...
0
votes
1answer
79 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 ...
2
votes
1answer
722 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 ...
3
votes
1answer
305 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 ...
1
vote
1answer
156 views

Choosing primes in the Paillier cryptosystem

In the first step of key generation phase in Paillier cryptosystem given here. It's given that ( length($p$) == length($q$) )$\implies$ gcd$(pq,(p-1(q-1)))$=1 where length($k$) = # bits in ...
1
vote
0answers
601 views

Hill cipher key space

Key space is the set of all possible keys that can be used to generate a key. We using the number of valid key to describe it. I've given a hill cipher of block size $k$ over alphabet of size $p$, ...
8
votes
2answers
614 views

Trial divisions before Miller-Rabin checks?

I'm trying to understand prime number generation (more correctly, the primality checking) as described in Handbook of Applied Cryptography. The context is circa pages 145 - 150, and specifically ...
2
votes
1answer
197 views

Given p and q of DSA how do you show they are prime?

I am given p = 4916335901 q = 88903 and am asked to show these are prime as well as q|(p-1) in DSA. I am unsure on how to ...
1
vote
1answer
175 views

Modulo properties of two prime numbers

I am supposed to prove that x = y mod (p*q) <=> x = y mod p and x = y mod q with p and q are prime numbers. It somewhat sounds reasonable to me, but unfortunately I don't have any clue how to prove ...
1
vote
2answers
128 views

Three different numbers with x³=x mod p

p is a prime greater than 2 and $a \in \mathbb{Z}_p$. Why are there exactly three solutions for a³ = a mod p? Obviously 0 and 1 are both in $\mathbb{Z}$ and valid solutions, but that still means, ...
2
votes
1answer
145 views

Pick faster private exponent

I recently tried to send 1536-bit modulus CSR to COMODO. They refused to sign the certificate. I later found out that it's because NIST mandated 2048-bit modulus on the SSL certificate. I think it's ...
-1
votes
1answer
303 views

How can I convert numbers into prime numbers?

I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers? Obviously I'd like it to be collision ...
2
votes
2answers
994 views

Does the secret key used in AES have to prime?

I’ve looked around this site and the web quite a bit, but can’t find a definitive answer on whether or not the secret key $k$ used in the AES crypto-system has to be a prime number? Or can you just ...
0
votes
1answer
54 views

From Factorisation of semiprimes to breaching confidentiality

If someone or some group found an efficient way to factor large composites with two distinct prime divisors, would this make it easier to decode any messages?
1
vote
1answer
189 views

Are the RFC3526 MODP groups Schnorr groups?

I was wondering if a group like the 1536-bit MODP Group from RFC 3526 was a Schnorr group? A Schnorr group must apparently have: $p$ and $q$ being primes $p = q\cdot r+1$ $1 < h < p$ ...
7
votes
1answer
3k views

Generating Random Primes

Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version". I'm implementing some homomorphic encryption ...
5
votes
1answer
331 views

How are trapdoor functions developed/found and where can I find existing ones?

Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is Prime Factorization, used in cryptosystems such as RSA How are these trapdoor ...
1
vote
1answer
146 views

Modular exponentiation with Chinese Remainder Theorem

I'm learning modular exponentiation with Chinese remainder theorem. I found a great answer from below How can I use eulers totient and the chinese remainder theorem for modular exponentiation? But I ...
2
votes
2answers
310 views

RSA: What happens to restrictions of plaintext n, dependent on p and q?

Ok - i will try to ask my question as clear as possible. Im getting a little deeper into the RSA-cryptosystem. At one point i'm a little confused. We have a plaintext $x$ and ciphertext $y$, with $x ...
1
vote
1answer
284 views

Generating Diffie-Hellman parameters efficiently

I am working on an Android project for school and I am supposed to do a DHKE (Diffie Hellman Key Exchange). Everything works well. The problem is that it takes a lot of time (really a lot) to ...
4
votes
1answer
525 views

Security of Pohlig-Hellman exponentation cipher?

I am looking into implementing Pohlig-Hellman exponentation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. ...
2
votes
2answers
335 views

Random numbers for Rabin-Miller primality tests

I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following ...
-2
votes
3answers
2k views

How can I find the prime numbers used in RSA?

I got this question in a local hacking event, but I couldn't solve it. Problem Statement ---- Continuing their snooping habit, NSA kept bugging Alice's communication. Resorting to the age old ...
5
votes
1answer
218 views

Is it possible to fool Miller-Rabin test?

It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without ...
1
vote
1answer
348 views

What exactly is inside a private key?

May sound stupid to many, but I would like to have some pointers on what exactly is contained inside a private key. I have decent understanding of public/private keys/certificates (have created them ...
-1
votes
1answer
2k views

why RSA uses Semiprime numbers? [duplicate]

Why does RSA use semiprime numbers? Why not just use any big number ?? What is the advantage of the two original numbers being prime? Because factoring any big number will be difficult
0
votes
1answer
250 views

What is the difference between, and security of $Z_p$ and $F_p$?

While reading some papers, I found that sometimes $Z_p$ was used but sometimes $F_p$ was used ($p$ is prime). Usually, the author will only use their subgroups like this: choose a big prime factor of ...
1
vote
0answers
218 views

Best group if one wants the discrete log problem to be hard?

Suppose one is implementing a cryptographic scheme over a group where one needs the discrete logarithm to be hard - what is the recommended group to use? I'm looking for a group where calculations are ...
2
votes
1answer
466 views

Prime number theorem - RSA

I am having trouble understanding the prime number theorem. As part of some revision for an exam, I am trying to answer the following questions (but seeing as I don't understand the concept of the ...
2
votes
0answers
103 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 ...
1
vote
2answers
167 views

Would this program be useful in cryptography?

I know nothing of encrypting. I'm not even sure how to tag this. I wrote a program that can calculate this pretty quickly on my macbook pro 2.3GHz IntelCore i7. The two exponents are Mersenne primes, ...