All Questions
Tagged with cryptography elementary-number-theory
209
questions
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
0
votes
1
answer
107
views
Find all pairs of keys $(a, b)$ for affine ciphers.
The question is as follows:
Find all pairs of integer keys $(a, b)$ for affine ciphers for which
the encryption function $c = (ap + b) \bmod 26$ is the same as the
corresponding decryption function.
...
- 105
1
vote
1
answer
49
views
Modulo composition confusion [duplicate]
In a cryptography lecture, I have run into a equation such that
$$y_i=e(x_i)=x_i+s_i(mod2)$$ $$x_i=d(y_i)=y_i+s_i(mod2)$$ where $e()$ means encryption and $d()$means decryption in Stream ciphers.
...
user1239778
0
votes
0
answers
31
views
Why is RSA encryption exponent always odd/never even? [duplicate]
I remember my professor mentioning that RSA encryption fails when $e$ is odd, but cannot seem to figure out why it is so, and can't find a proof in a textbook/online. I tried verifying it by proof-by-...
- 137
1
vote
2
answers
111
views
If $x^e \equiv y^e \pmod N $, is $x \equiv y \pmod N$ where $\gcd(e,\phi(N))=1$?
Let $x,y,e,$ $p$, and $q$ be any integers where $N= pq$ and $e$ is coprime to $(p-1)(q-1)$ . I am wondering whether $x^e \equiv y^e \pmod N $ implies $x \equiv y \pmod N$, and if so how to show this. ...
- 3,019
0
votes
2
answers
80
views
Proof of correctness of RSA sufficient? [duplicate]
In a lecture I am taking the following proof for the RSA cryptosystem is given:
$m^{ed} \equiv m^{ee^{-1}} \equiv m^1 \equiv m \pmod N$
where $N = pq$; $p$,$q$ prime; $2 < e < \phi(N)$; $e$,$\...
- 249
0
votes
0
answers
81
views
How difficult this RSA cracking algorithm is.
If the way to crack the RSA algorithm is knowing the factors of a number. How easy can the factors be obtained by taking the reverse 'long product'?.
For instance, if you have the product of three ...
0
votes
1
answer
47
views
$(x^e)^{\hat d} \equiv x \mod n$ for all $x$ with $\gcd(x,n) = 1$ and $\hat d \equiv 71 \mod 126$.
Suppose that in an RSA algorithm, we have the public key $(n,e)$ where $n = 2413, e = 323$.
(a) Given that $2413 = 19 \times 127$, find the private key $(n,d)$.
(b) Explain why $(x^e)^{\hat d} \equiv ...
- 12.7k
2
votes
0
answers
81
views
Finding primitive roots including negative sign
I commonly run into the following question such that if $p$ and $q=4p+1$ are both odd primes prove that $2$ is primitve root modulo q . However , i could not prove it for other number that are given ...
user1121946
0
votes
1
answer
81
views
mathematical issue while encrypting/ decrypting in CRT. [closed]
I have a plaintext to be decrypted as follows:
$m = 2^{953} \bmod 1147$.
However, when I type $2^{953}$ in the calculator it gives me a math error!
So, how can I solve this equation? Even though, I ...
- 21
0
votes
1
answer
161
views
xor values of character and space vs xor value of character and character
How do i prove that xor of character and character is always less than 64 while xor of a space and a character is greater than equal to 64 .
NOTE :that all english characters have ascii in [64, 127] ...
- 696
1
vote
2
answers
56
views
How to prove that $f(x)=x^3 \pmod{pq}$ is bijective for any non negative integer $x<pq$ where 3 is not a factor of $p-1$ and $q-1$? [duplicate]
I am reading a book on cryptographic programming and I found an example without proof.
How to prove that $f(x)=x^3 \pmod{pq}$ is bijective for any non negative integer $x<pq$ where 3 is not a ...
- 351
0
votes
2
answers
42
views
When does $B^x \equiv B^{2^{2^i}}\ (\textrm{mod}\ N)$ imply $(B^x)^x \equiv B^{2^{2^{i+1}}}\ (\textrm{mod}\ N)$
If $B^x \equiv B^{2^{2^i}}\ (\textrm{mod}\ N)$, under what conditions must it be true that $(B^x)^x \equiv B^{2^{2^{i+1}}}\ (\textrm{mod}\ N)$?
We can take for granted that $N$ is the product of two ...
- 103
1
vote
0
answers
51
views
Would encrypting a message twice with RSA with different keys be more secure that once?
This was a practice problem for a class. The class is over now and I never solved it, so I thought I'd ask here.
Let's ignored the fact that adding extra security to single textbook RSA is unnecessary....
- 23
-1
votes
1
answer
36
views
Need help understanding the proof of correctness of deciphering algorithm in the original RSA paper. [duplicate]
In the paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" by R.L. Rivest, A. Shamir, and L. Adleman, they prove correctness of deciphering algorithm by following ...
- 45