# Tagged Questions

66 views

### Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
59 views

### choose two prime numbers of length $k$

Maybe the following is a stupid question, if it is I apologize, and I encourage you to close my post. Suppose that I want to encrypt a message with the RSA cryptosystem; the starting rule is the ...
35 views

### Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
30 views

### Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
61 views

### Determine a generator of $\mathbb{Z}^*_{11}$ manually.

What is the best/standard way to do this manually? Could you describe a solution in a step-by-step fashion.
53 views

### Manually performing the Miller-Rabin probabilistic primality test

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.
66 views

### Manipulating square roots mod p (prime) and when is $g^{ \frac{x}{2}} = p - z_1 \pmod p$ true?

tl;dr: If $z_1 = g^t \pmod p$ is one of the square roots of $g^x \pmod p$ such that $\frac{p-1}{2} \leq t < p-1$. Then, does $p-z_1 = g^{\frac{x}{2}} \pmod p$ hold true? Say that we define a ...
72 views

### Relating calculus to RSA and/or prime factorization?

I'm writing a math paper on RSA and it would be nice if it had some calculus in it. Is RSA directly related to calculus in any manner? This can include proving theorems, generating keys, or cracking ...
64 views

### El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
59 views

### If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/k} \equiv 1$ (mod n)

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/x} \equiv 1$ (mod n) such that $a^{n-1} \equiv 1$ (mod $n$) and x is prime such as $x |(n-1)$. I am solving the bigger proof ...
67 views

### Encrypt the message m = 4 [closed]

a) Let p = 11. If e = 7 , show the steps and find d. b) Encrypt the message m = 4 c) Decrypt the result of part (b). GCD(7,p-1) = 1 there is a d such that (m^e)^d = m d satisfies ed - (p -1)k = 1
79 views

### Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
64 views

### Calculation using prime number theorem

Fix a (large) number N and suppose that Bob chooses a random number n in the interval $1/2N ≤ n ≤ 3/2N$. If he repeats this process many times, prove that approximately $1/ ln(N)$ of his numbers will ...
329 views

### Extension of Fermat's little theorem with Carmichael numbers

I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this ...
109 views

### Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :) this is a link to a previous post which quickly ...
150 views

20k views

### Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
1k views

### How to work RSA encryption/decryption

I need an array populated with characters and integer keys for each, and I want to, using this set, encode messages, and then decode them later on . Essentially I am trying to write RSA algorithm for ...
1k views

### Trying to calculate RSA decryption key

I am testing a piece to encrypt and decrypt messages, and I am not 100% on why the algorithm does not seem to work as expected. My test encryption key $e =27$. My primes $p = 263$ and $q = 911$. And ...
834 views

### If the Goldbach Conjecture is True, does it make it easier to find large primes?

I was just reading Is every positive nonprime number at equal distance between two prime numbers? (current hot topic) and was reflecting on the fact that computing security (cryptography) is based ...
309 views

### RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
162 views

### Proof of Primality Testing

I am learning some Cryptography and I came across this exercise where I have to make the following proof (translated from German, so I hope it is accurate). Proof the following assertion: Let \$n ...