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

1
vote
2answers
68 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?
15
votes
5answers
395 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 ...
0
votes
0answers
72 views

How do I find a random BigInteger smaller than another random BigInteger? [migrated]

How do I Select a random element α ∈ Z∗p? P is a random 1024 bit prime BigInteger. Here is how I find BigInteger p: ...
1
vote
1answer
66 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
39 views

Primality of number 1 [migrated]

Is number 1 prime as per the definition of prime numbers? Because as per the definition for being prime it should be divided only by 1 and number itself.
1
vote
1answer
87 views

Timelock puzzle improvment

I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle ...
-2
votes
0answers
41 views

Factoring a number who has factors with same number of digits

I am working on a factoring problem. I have a number that is a product of two prime numbers, both with same numbers of digits (20-30 digits). I was searching online for algorithms that are good for ...
0
votes
0answers
67 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
195 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
54 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 ...
0
votes
1answer
73 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 ...
3
votes
1answer
61 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: ...
6
votes
3answers
520 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?
3
votes
2answers
250 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 ...
1
vote
1answer
169 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 ...
1
vote
1answer
68 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.
1
vote
1answer
235 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 ...
2
votes
1answer
116 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
53 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 ...
1
vote
1answer
144 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
84 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 ...
3
votes
1answer
821 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. ...
8
votes
2answers
296 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
121 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
vote
2answers
120 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, ...
1
vote
1answer
106 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 ...
2
votes
2answers
556 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
48 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
81 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$ ...
4
votes
2answers
277 views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
3
votes
1answer
127 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 ...
-1
votes
1answer
247 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 ...
1
vote
0answers
178 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$, ...
1
vote
1answer
106 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
1answer
154 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 ...
3
votes
1answer
210 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 ...
2
votes
2answers
194 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
164 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 ...
2
votes
2answers
210 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
1k 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
156 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
218 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
458 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
1
vote
0answers
156 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
0answers
74 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
162 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, ...
1
vote
0answers
190 views

Factoring large numbers

I am trying to factor few integers that are each between 115 and 135 digits long. I have just, little over a month ago, began my study of Cryptography. I was wondering if anyone knew of any efficient ...
2
votes
1answer
148 views

Good Encryption Exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are ...
2
votes
1answer
355 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
1answer
48 views

How can I evaluate the congruency of an AKS primality test?

Despite the fact primality test is a mathematical issue, it plays a part on the security of many cryptosystems such as RSA. I was trying to understand how it works until I came to the following ...