1
vote
0answers
36 views

Find f(x,y) = 1 if(x=y) else 0 (f must only do addition/substraction multiplication or division)

This maybe more of a computer science problem but maybe the solution lies in number theory. Given integers x,y, find F(x,y) = 1 if x=y else F(x,y) = 0 The obvious solution Negate( x-y ) cannot be ...
1
vote
1answer
58 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
57 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 ...
1
vote
2answers
114 views

RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
0
votes
0answers
57 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
42 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
2answers
41 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
121 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
75 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
102 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
238 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
67 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
80 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
42 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
99 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
222 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
63 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
45 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
72 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
163 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
60 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
62 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 ...
2
votes
1answer
172 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
84 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
356 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
75 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
64 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
94 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
1answer
191 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
88 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
26 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
356 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
50 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
198 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
346 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
5k 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
362 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
446 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
81 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 ...