3
votes
4answers
58 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 ...
1
vote
1answer
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 ...
0
votes
1answer
29 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 ...
1
vote
2answers
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.
2
votes
2answers
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$.
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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$ ...
0
votes
0answers
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 ...
-1
votes
1answer
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
0
votes
2answers
78 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 ...
0
votes
1answer
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 ...
0
votes
1answer
327 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 ...
1
vote
2answers
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 ...
0
votes
1answer
150 views

Quadratic reciprocity - legendre symbol $\neq$ jacobi symbol

I want to calculate wether $\exists x : x^2 \equiv 123 \mod 11\cdot 13$ or not. I do know that in terms of the legendre symbol follows that $\neg(\exists x: x^2 \equiv 123 \mod 11)$ and $\neg(\exists ...
14
votes
1answer
962 views

If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?

I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...
1
vote
0answers
63 views

How are prime numbers used to facilitate modern encryption? [duplicate]

Possible Duplicate: Why are very large prime numbers important in cryptography? I'm interested in how the algorithms for creating key pairs to be used in dual key encryption work. I have ...
1
vote
1answer
46 views

Generating a number of a specific order

Here is what I have: select $p$ such that $p - 1$ has a large prime factor $t$: $p - 1 = tu$, where $u$ is a random number $n = p^2 q$, where $q$ is prime pick random $g < n$ and compute $g_p = ...
17
votes
2answers
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
1
vote
2answers
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 ...
2
votes
1answer
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 ...
6
votes
3answers
831 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 ...
3
votes
1answer
266 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 ...
1
vote
1answer
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 ...
15
votes
3answers
605 views

RSA in plain English

I'm a computer science student, I'm not a mathematician, I don't know anything about number or group theory. I'm looking at RSA, and I want to understand it. I know what Fermats's little theorem and ...
23
votes
2answers
9k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...