All Questions
Tagged with cryptography totient-function
27
questions
0
votes
1
answer
71
views
Prove that if $e.d \equiv 1 \bmod (p-1)(q-1)$ then it’s impossible to have $e.d \equiv 1 \bmod pq$
I am studying R.S.A. cryptosystem and here is the question that came to my mind. Let’s pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler’s totient function:
$$
\phi(n) = (p - ...
-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
1
vote
0
answers
47
views
Understanding Euler's Totient Rule in RSA [duplicate]
I'm trying to understand the use of Euler's Totient Theorem in RSA. It is defined as : if $a$ is coprime with $n$ then $$ a^{\phi(n)}\equiv{1 modn} $$
I am unable to understand how the above implies ...
- 195
2
votes
1
answer
591
views
What's the REASON behind the mathematics of RSA?
Being a non mathematics student, I started to understand RSA. Now I am at a place where I can show someone how to do it or prove it mathematically. What I don't understand is why we do the maths that ...
- 39
0
votes
1
answer
378
views
Need to understand Lagrange's theorem and how it's applied in RSA
When I first started studying RSA, I found that I need to know Euler's theorem, to understand that I need Fermat's theorem, and to understand that, I need the order theorem of Lagrange which I am ...
- 39
2
votes
1
answer
59
views
Algorithms for encryptor in RSA
In RSA we denote encryptor as $E$ such that:
$$\gcd(E,\phi(p,q))=1\tag{where $p,q$ are primes}$$
I know if for all prime factors $c$ of $\phi(p,q)$, $c \not\mid E$, that we can choose this $E$ as a ...
- 5,283
0
votes
2
answers
527
views
How can I find the inverse of number using Fermat's Little Theorem or Euler's Theorem? [closed]
Specifically the inverse of 101 and with n = 31200.
$101^{-1} \mod 31200 $
- 3
1
vote
1
answer
175
views
RSA with small encryption exponent
In RSA: Fast factorization of N if d and e are known a comment under the OPs question stated that if the encrytion exponent $e$ is small compared to $N=p\cdot q$ for the RSA-primes $p,q$ (like $e<\...
- 874
3
votes
1
answer
236
views
Factorization of large (60-digit) number
For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$
To calculate a private exponent in the encryption ...
- 1,218
0
votes
2
answers
41
views
What am I doing wrong decrypting this RSA message?
Here's a basic understanding I have of how RSA works from my notes.
Alice generates two primes $p$ and $q$ such that $n= pq$ and finds a $k$ such that $gcd(k,(p-1)(q-1))=1$.
She then finds an s ...
- 1,363
2
votes
3
answers
89
views
Calculate modulo solution of a number with a high exponent [duplicate]
I need some help calculating the solution for the following equation:
$ 4^{217} = x \text{ (mod 391)} $
Using power rules ($4^{217} = 2^{434}$) and Eulers theorem ($\phi(391) = 352$) I was able to ...
- 31
1
vote
1
answer
255
views
RSA decryption coefficient [duplicate]
Sorry, I know there are several threads about RSA encryption and how to calculate $d$. But there is a thing I still don't understand. So you calculate $d$ by using the following expression (see here):
...
- 13
0
votes
1
answer
131
views
proving that $x \rightarrow x^e \pmod m$ is not one to one
Let $m=pq$ where $p,q$ are primes. Prove that if $e$ is not coprime to $\phi(m)$, then the mapping $x \rightarrow x^e \pmod m$ from $Z_m^*$ to $Z_m^*$ is not one-to-one.
My attempt: Let $s,l$ be ...
1
vote
1
answer
54
views
RSA Cryptography: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$
The modulus, $n=8633$, is given (it's simple to find $p$ and $q$ such that $n=pq$, i.e. $p=89$ and $q=97$) and the task is to find an encoding exponent, $e$, such that the correpsonding decoding ...
- 592
2
votes
1
answer
1k
views
how to hand calculate RSA decryption exponent (using small numbers)
This is a simple exercise to help my personal understanding of RSA. I'm not trying to do anything that will have real world security.
I want to compute the RSA decryption exponent ...
- 293