1
vote
1answer
49 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
1
vote
2answers
55 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
0
votes
0answers
49 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
2answers
35 views

To solve for the decryption exponent, why do we solve the congruence $de = 1 (mod (p-1)(q-1))$

So we choose two large primes p and q and multiply them together to get n. We also pick an encryption exponent e and so for any message m, we can compute m^e (mod n) which is our ciphertext c. So ...
0
votes
1answer
31 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
106 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
1
vote
2answers
72 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
1
vote
1answer
108 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
0
votes
2answers
100 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
2
votes
1answer
236 views

Prove: b passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$

Question: Let $p$ be a prime and $b$ an integer with $\gcd(b,p) = 1$. Prove: $b$ passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$. I know that if $b^{p-1}\not\equiv ...
3
votes
1answer
40 views

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$? My doubt was specifically why, when raising to the power of the decryption key d we get a unique number ...
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
78 views

Explanation of $d^{-1}$ in modular arithmetic [duplicate]

I wasnt quite sure what to name this question, so that's what it is. I'me working on an encryption system, and I need modulus. I already asked a question on this, here, and I cannot figure out the ...
2
votes
1answer
39 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
0
votes
2answers
98 views

Define ≡ in this situation?

"Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$." (number $5$). I'm looking at this, and i'm not sure what the $\equiv$ means in this ...
0
votes
0answers
197 views

Why does RSA have to use Euler's Totient function?

$$\begin{aligned}m^{ed} &\equiv m\bmod n\\ ed &\equiv 1 \bmod \phi(n)\\ \end{aligned}$$ Why does the modulus of the modular multiplicative inverse have to be the totient function? Won't any ...
0
votes
3answers
61 views

Which divisors produce unique moduli? (for RSA encryption)

Sorry if this question is confusing, I'm still confused by the whole thing. I'm trying to understand how RSA encryption works, but I'm having trouble with the modulus part. For RSA to work, $c=m^e ...
1
vote
2answers
42 views

Modulus Function

I am watching a tutorial an i saw how to use the modulus they said if 20/7 = 2.8571422857 you must subtract the whole number then multiply it by the divisor now am trying to understand a Public key ...
1
vote
1answer
69 views

Primality test with polynomial congruence (preliminary to AKS algorithm)

I have trouble in understanding the proof of this primality criterion: $n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$. In ...
2
votes
0answers
155 views

Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
0
votes
1answer
57 views

RSA Encryption - why does it guarantee a unique cipher?

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext. How do we know all message $M$ (for ...
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
vote
1answer
161 views

cryptology beginner book

I am taking a number theory course this semester which includes a brief intro to the field of cryptology including only : Applications to Cryptology, Character Ciphers,Block and stream ...
1
vote
0answers
80 views

Understanding Quadratic Sieve Algorithm

I am studying Cryptography and came upon the quadratic sieve algorithm. However, I am having hard time understanding how the algorithm works. I kind of understood how the steps are followed through ...
1
vote
1answer
43 views

Decrypting a message?

I would like to ask for a little help about the following problem, i got stuck in it and have no idea how to proceed to get the answer which Wolfram Alpha gives (of course, i am not allowed to use the ...
1
vote
0answers
76 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
0
votes
1answer
333 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 ...
0
votes
0answers
74 views

How to calculate RSA Cryptography for small prime numbers?

Probably duplicate of Why are very large prime numbers important in cryptography? But my question is,what if we start with two small prime numbers say $p = 3$, $q = 5$ and $n = pq = 15$, $\phi(n) = ...
1
vote
1answer
62 views

RSA encryption theory - modulo theory

I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem ...
0
votes
1answer
88 views

RSA cryptosystem: If $k$ is a multiple of $\phi(N)$, then $k=2^t r$ with $r$ odd and $t\geq1$

I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3. Fact 1: Let $(N,e)$ be an RSA public key. Given the private ...
-2
votes
2answers
280 views

RSA: Prove that all messages encrypt to itself [closed]

RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
2
votes
1answer
188 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
2
votes
1answer
55 views

Formula/Algorithn for Exponential factoring?

Given $s = a^b$ find $a$ and $b$. my first algorithm was the obvious brute force method of checking all $b$ roots or dividing by all possible $a$. But I am wondering if there is a more efficient ...
1
vote
1answer
66 views

Show that the decryption transformation for the El Gamal cryptosystem works.

Want to show that, if $P$ is the original plaintext block and $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then $$(\gamma^a)'\delta \equiv P \pmod p$$ So, we have: $\gamma = \alpha^k ...
0
votes
1answer
85 views

Compute the output of 97 after a byte substitution in AES?

I understand the framework of the calculation, however I am struggling to determine the inverse of 97 in GF(256). Any straight forward explanation would be greatly appreciated. My resources have not ...
4
votes
1answer
153 views

Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
0
votes
0answers
25 views

Computing discret logarithm $log_{g}(h)$ such that $g,h$ are generators for the cyclic group $Z^{*}_{p}$

Let $p$ be a prime number, $g, h$ be generators of the cyclic group $Z^{*}_{p}$ , and $f$ be defined as: $f : \lbrace 1, . . . , p − 1\rbrace^{2} → Z^{∗}_{p}; (x,y) \rightarrow g^{x}h^{y}\;mod\;p$. ...
1
vote
1answer
317 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
1
vote
0answers
48 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
2
votes
0answers
69 views

(Please check working) Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$

Please check the working and final answer to the question: Question: Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$ My working: $\phi(3737) = \phi(37) \times ...
3
votes
1answer
1k views

RSA solving for $p$ and $q$ knowing $\phi(pq)$

I am trying to find primes $p$ and $q$ in the RSA algorithm given $n = pq$ and the value of $\phi(n)$. I know the following: $\phi(n) = (p-1)(q-1) = pq - p - q + 1$ Solving for $p+q = pq - \phi(n) + ...
1
vote
3answers
108 views

Given RSA encoding function $E: x\to x^7 \pmod{6161} $ find decoding function D

So far I got: $7\alpha \equiv 1$ mod $\phi(6161)$ $\phi(6161) = \phi(61) \times \phi(101) = 6000$ $7\alpha \equiv 1$(mod $6000)$ At this point we are supposed to do euclid's algorithm and somehow ...
0
votes
1answer
196 views

Simple modulus algebra - rabin karp weird implementation

I'm studying the Rabin Karp algorithm and something isn't clear about the modulus algebra: Let's suppose I have all base-10 numbers for simplicity's sake $14159 = (31415 - 3 \cdot 10^4) \cdot 10 + ...
4
votes
2answers
342 views

Is the subgroup of quadratic residues modulo $N = pq$ a cyclic group if $p$ and $q$ are primes?

I saw this question When is the group of quadratic residues cyclic? and the answers to that. I have a similar question. Assume $N=pq$ where $p$ and $q$ are primes. We know that $\mathbb{Z}^*_N$ is ...
0
votes
2answers
57 views

Security of a particular cryptosystem

I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution ...
5
votes
4answers
4k views

Practical method of calculating primitive roots modulo a prime

How are generators of a (large prime) set calculated in popular programs such as pgp and libraries such as java's bouncycastle? i cannot imagine them just churning away at every value between 2 and p ...
2
votes
1answer
354 views

Decrypting a Message Encrypted in RSA Using Two Coprime Encryption Keys

The last question of our number theory final review is as follows: The same plaintext $P$ is encrypted in RSA using two coprime encryption keys $e_1$, $e_2$. Show how this message can be decrypted ...
0
votes
2answers
435 views

Cracking a Simple RSA Encryption

Show that if the encryption exponent $3$ is used for the RSA cryptosystem by three different people with different moduli, a plaintext message $P$ encrypted using each of their keys can be ...
2
votes
0answers
80 views

Interesting Characteristic About the RSA Cryptosystem

I know that decryption in the RSA cryptosystem works because$$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv ...
0
votes
1answer
99 views

Number of divisions using trial division to factorize the product of two k-digit primes

I'm more of a programmer than a Mathematician so please bear with me if my question is too trivial. I am looking up RSA specifically the key generation bit. Using Trial division, I know that it would ...