I have to replicate the key set up process of RSA public encryption algorithm.  Basically I am given two random primes, $P = 7$ and $Q = 5$.  I calculate the following   $N = 5 \cdot 7 = 35$  $O(N) = (p-1)(q-1) = 4\cdot6 = 24$  $e = 7$ -> this is the encryption key  To find the decryption key I need to solve the following equation:  $e*d \equiv 1$ (mod $n$) where $0 \le d \le n$.  I have watched YouTube videos where they explain how to calculate the modular inverse using Euclid's Algorithm, but after the first step I end up with:  $35 = 5(7) + 0$  In all the videos I saw, they usually end up with a remainder of $1$ so that they then set the equation to be equal to 1 and then they substitute to calculate the inverse modulo, but I just end up with      $35 = 5(7) + 0$   and I don't know how to proceed.
22367
I need help with this:  If a is an element of $\mathbb Z_n$ and $\gcd(a,n) &gt; 1$ , then a is not invertible.   First you show that if $a$ is an element of $\mathbb Z_n$ and $\gcd(a,n)&gt;1$, then there  is an element $b$ of $\mathbb Z_n$ and ($b$ is not equal to the zero element) from which $ab = 0$.   The second part I cant get. i.e. show if $b$ is not the zero element  and $ab=0$ then $a$ is not invertible.
1900
While calculating RSA encryption key we take modulo $\varphi(n)$ rather than modulo $n$. I can’t understand why it’s done this way.
19057
I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x &lt; b$ and $a$ and $b$ are not co-prime, given variables $a$, $b$ and $c$, as described by the equation below?   $ a x \equiv c \mod b $   For example, given  $ 154x \equiv 14 \mod 182 $, is there an efficient method for computing all the possibilities of $x$, without pure bruteforce?  Please note that I'm not necessarily asking for a direct solution, just a more optimized one.    I do not believe that the Extended Euclidean Algorithm will work here, because $a$ and $b$ are not co-prime.   Edit:  Follow up question, since the first one had a shortcut:  Could the be computed efficiently as well?  $12260x \equiv 24560 \mod 24755$.  $107$ needs to be one of the computed answers.
7289
I understand there is a method for solving simultaneous modular equations. For example; $$x = 2 \mod{3}$$ $$x = 3 \mod{5}$$ $$x = 2 \mod{7}$$ We find numbers equal to the product of every given modulo except one of them - giving $5 \cdot 7$, $3 \cdot 7$ and $3 \cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by: $$x = 2 \cdot (5 \cdot 7) \cdot 2 + 3 \cdot (3 \cdot 7) \cdot 1 + 2 \cdot (3 \cdot 5) \cdot 1 = 233 = 23 \mod{3\cdot5\cdot7}$$  But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0\le x \lt 3\cdot5\cdot7 \mod{3\cdot5\cdot7}$ but can someone please explain why this method finds this value of x?
89957
I have been trying to solve   It is not an ongoing contest problem.  We can calculate $n$th Bell number modulo a prime number greater than $10^7$ in $O(n)$ arithmetic operations, using this formula $$B_n=\sum_{k=1}^{n}\frac{k^n}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}$$ We can store the partial inner sum for future use, without calculating again and again. For example $B_{10^7}$ $\text{mod}$ $1000000007$ $=29987405$.  But in the problem the modulus is $30!$, so we can't do modular inverse operations. I tried to reduce the formula to $$B_n=\sum_{k=1}^{n}\frac{k^n!(n-k)}{k!(n-k)!}=\frac{1}{n!}\sum_{k=1}^{n}\binom{n}{k}k^n!(n-k)$$ $!n$ denotes subfactorial function.  I am stuck here. Can anyone help?
31547
I was given a cryptography question during an interview the other day.   Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.   1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.   Figure out an algorithm that uses this one and can decrypt any message. Any ideas?
111312
I've been trying to decrypt a message encrypted with Rabin as a challenge.  I'm very new to cryptography and these challenges so much of this is new. I've factorised n and determined that p=q which I understand to be incredibly weak.  After many hours I discovered that the proposed decryption using extended gcd will not work. A similar post on this site suggested using Tonelli Shanks to get the roots, which I have done.  It then went on to say to use Hensel to then get the original values which will then help me decode the message, however I am unfamiliar with how to implement this and so far have not been able to get a sensible solution so would like to ask for help. My values are: n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121 c = 60176314581676071043291067556352196274798660837188399828657574988742539250919925123769575021091715252070984470036260674221672743791229186519807702970426856963367776191049481817101068301897617186674960557150362771617316082251276579987076557148986523477838971190589062577795308359830070072697195634741564991953 p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511 root0 = 2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364  root1 = 5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147
3478
Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this site (where the extended Euclidean Algorithm is mentioned mainly) as well as looked up some books but there is no mention of this. Am I going wrong somewhere or is this a correct method of finding modular inverses? Also can't we find the Bézout's coefficients by solving the corresponding diophantine equation instead of using the extended Euclidean Algorithm?
48820
I stumbled across this problem  Find $\,10^{\large 5^{102}}$ modulo $35$, i.e. the remainder left after it is divided by $35$  Beginning, we try to find a simplification for $10$ to get: $$10 \equiv 3 \text{ mod } 7\\ 10^2 \equiv 2 \text{ mod } 7 \\ 10^3 \equiv 6 \text{ mod } 7$$ As these problems are meant to be done without a calculator, calculating this further is cumbersome. The solution, however, states that since $35 = 5 \cdot 7$, then we only need to find $10^{5^{102}} \text{ mod } 7$. I can see (not immediately) the logic behind this. Basically, since $10^k$ is always divisible by $5$ for any sensical $k$, then: $$10^k - r = 5(7)k$$ But then it's not immediately obvious how/why the fact that $5$ divides $10^k$ helps in this case. My question is, is in general, if we have some mod system with $a^k \equiv r \text{ mod } m$ where $m$ can be decomposed into a product of numbers $a \times b \times c \ \times ...$, we only need to find the mod of those numbers where $a, b, c.....$ doesn't divides $a$? (And if this is the case why?) If this is not the case, then why/how is the solution justified in this specific instance?
122066
I am having trouble with understading how inverse totient function works. I know it can have multiple solutions but I don't understand how to find all of them for bigger numbers. For example how would one approach to problem of solving this equation:  ϕ(n) = 180  I do understand that one should represent ϕ(n) by product rule and somehow conclude numbers by combining product rule expression for ϕ(n) to get all numbers n. But it seems as very long process that I don't understand. My question is how I should think when looking at prime numbers expression for ϕ(n) and how should I eliminate some results? I was trying searching other similiar question and I still can't find some general algorithm for solving this problem.  Thanks!  EDIT: I would like to know how to calculate this problem by hand
44367
In an RSA-encryption scenario, Bob's public key pair $(n, e)$ is $(143, 43)$. An attacker Mallory tries brute-force and comes to $d = 7$ as the private key. The value of $φ(143) = 120$ is not known to Mallory. However from $43 \cdot d \equiv 1 \bmod 120)$, one can calculate the first positive element $d = 67$ from multiplicative group $d = 120 + 67n$ and $n \in \mathbb{Z}$ $d = 7$ clearly doesn't fit in that multiplicative group, so how come it can successfully decrypt the encryption?
35258
I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted messages.  Given the three pairs of public keys $(N_i,e)$ and the encrypted messages $c_i=m^e\bmod N_i$ , how do I decipher the original message $m$ ?
79550
Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.  $n = 8192$ bits; $c = m^e \mod n$;  In essence my question is how does the CPU deal with this huge modulus?
34494
Let $N=pq$ where $p$ and $q$ are safe primes. If the adversary knows the inverse of $p$ mod $q$ and the inverse of $q$ mod $p$, can this help him factor $N$ or break the textbook RSA?
26908
Let $p, q$ be distinct odd primes, I would like to compute the number of solution $\mod p$ to the congruence $x^q \equiv 1 \mod p$. (Show that it's $gcd(q, p - 1))$  If $x^q \equiv 1 \mod p$, since $q$ is prime, this must mean that $x$ is either $1$ or has order $q$.   Hence, the problem reduces to finding the number of elements of $U_p$ which is either $1$ or has order $q$.  If $ q \nmid  p - 1$, then there is only one element, namely $1$.  If $q \mid p - 1$, then the number of elements of order $q$ is $\phi(q) = q - 1$, and so the number of solutions to the congruence $\mod p$ is $q - 1 + 1 = q$, and in either case the number of solutions is $\gcd(q, p - 1)$.  Does this look fine?
117732
Question 1: Denote $a \mod b$ as $a \% b$, where $a$ and $b$ are some integers  Evaluate 12^32475 % 21    The following is what I tried:    12^32475 % 21 = (12^3 % 21)^10825 % 21 = 6^10825 % 21 = ... = 6^433 % 21   But how to continue ?  Question 2:  I don't understand this: n-1= -1 mod n. Where is this from? And does this line become the next line?    Context: my class is discrete math for computer science. So far for related topics, it covers modular inverse, (extended) GCD algorithm, Fermat's Little Theorem and Chinese Remainder Theorem (CRT).
59037
I am a bit of a newbie to RSA encryption, so please be patient.  I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be about 2048 bits long.  However, we don't have a way of generating and verifying a 2048 bit prime number with 100% accuracy. The implementation for prime generation that gpg uses goes through 64 rounds of miller-rabin which is enough to give a prime probability of $1 - 2^{-128}$.  Given that these primes are only probabalistically prime, what happens if we selected composite values for p or q?  Does the RSA algo run into any sort of problem?  My guess is that there will be no problem and RSA continues to function normally (encryption and decryption both) because, if there was a problem, we could use that problem as a way to detect that the numbers are not prime. This would give us a really fast way to verify extremely large prime numbers. I am guessing this is not the case.  So, my conclusion is that RSA works with prime or composite p, q... but using composite p, q makes it easy to break the encryption (because its easier to derive p, q from n).  Is this conclusion correct?