1
vote
1answer
28 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
1
vote
1answer
26 views

Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice. ...
1
vote
2answers
22 views

reducing exponent in modular arithmetic

Im struggling with an example excercise because I have problemes to comprehend an step in the calculation $3^{36} \mod 59 = 3^{7} \mod 59$ How can I reduce the exponent $36$ to $7$? I tried it with ...
2
votes
1answer
34 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
12 views

$A^{-1}x \pmod{26}$ and coprime requirement in Hill cipher

I am reading Hill cipher from wiki page and I have been stuck on this thought for a while. Why is there a requirement for $\det(A)$ and $26$ to be coprime in Hill cipher ? Anybody familiar with Hill ...
1
vote
1answer
60 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
1answer
36 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
1
vote
1answer
27 views

finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
1
vote
2answers
40 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
0
votes
1answer
68 views

Public Key Scheme decryption. [closed]

You have been sent a message based on the following Public Key Scheme. 1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $ 2) Bob chooses integers $ e,d ...
1
vote
0answers
90 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
1
vote
1answer
43 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
0
votes
0answers
53 views

RSA Decryption - finding Private Key

Let p and q be primes and $e \in \mathbb{Z}^+$, with $\gcd (e, (p-1)(q-1)) = 1$. Let d be the inverse of $e \mod (p-1)(q-1)$. The decrption process where M is plaintext and C is ciphetext ...
0
votes
1answer
38 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
1answer
132 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
0
votes
1answer
89 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
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 ...
0
votes
0answers
253 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
64 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 ...
0
votes
1answer
64 views

Find the RSA factorization

I want to solve this exercise: Assume you have to do with an RSA System whose public parameters are (n,e)=(55,17). Now you can compute d. -->That's easy I've got d=33. You know a computer uses CRT ...
1
vote
2answers
46 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 ...
2
votes
1answer
35 views

Given four numbers $(a,b,e,n)$ is it possible to find $k$ such that $k^{e}a = b \pmod n$?

Let $n$ be a large given number. Also, $n = pq$ for some unknown primes $p,q$. The Euler Totient function, $\varphi(n) = (p-1)(q-1)$ is not known or easy to calculate. $e$ is a given number co-prime ...
1
vote
1answer
19 views

Given three numbers $a, b$, and $n$, is it possible to find a number $k$ such that $ka\equiv b\pmod{n}$?

I came up across this problem working on some (purely academic) attack on cryptographic schemes. Given any three integers $a,b,n$ such that $a<n,b<n$, I am interested in an integer $k$ which ...
0
votes
1answer
741 views

RSA encryption/decryption scheme

I've been having trouble with RSA encryption and decryption schemes (and mods as well) so I would appreciate some help on this question: Find an e and d pair with e < 6 for the integer n = 91 so ...
5
votes
3answers
69 views

Public Key Cryptography

Assuming that a message has been sent via the RSA scheme with $p=37$, $q=73$, and $e=5$, what is the decoding of the received message "34?" So far, I have $x^5 \pmod{37\times73} \equiv 34$. How do I ...
0
votes
0answers
63 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
53 views

computing the discrete log of $23^x \equiv 102 \pmod {431}$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong? "Alice and Bob agree to use a Diffie-Hellman key exchange with values p = 431 and primitive ...
0
votes
2answers
295 views

What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
2
votes
3answers
63 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
0
votes
0answers
48 views

Must the “n” in mod(n) always be prime?

I'm experimenting with mod(n) and have the following questions even after reading the Wiki page and numerous articles about the subject. Must mod(n) always be prime for cryptographic purposes? Is ...
1
vote
2answers
47 views

Proving that if $ed ≡ 1 \pmod{\frac12 φ(n)} $, then $y^{ed} ≡ y \pmod{ n}.$

This is actually the third step of the problem. It's preceded by these questions that I'm sure are supposed to lead me to solution. $n = pq$, p and q distinct odd primes First I'm supposed to show ...
1
vote
3answers
235 views

RSA encryption without a calculator

I'm doing an RSA encryption and to get part of the solution I need to solve $$C=18^{17} \pmod{55}$$ How would I solve this problem without a calculator Thanks in advance
3
votes
4answers
312 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
3
votes
2answers
111 views

Why modular arithmetic in secret sharing?

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a ...
2
votes
1answer
92 views

Modular exponentiation WITHOUT modular exponentiation

Given that 719 is prime, find the least positive residue of $11^{721} (mod\ 719)$, without using modular exponentiation. So, I know how to use modular exponentiation and have done it to get the ...
12
votes
6answers
953 views

How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
0
votes
1answer
289 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
1
vote
0answers
46 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
3
votes
1answer
110 views

Is the number of quadratic nonresidues modulo $p^2$, greater than the number of quadratic residues modulo $p^2$?

Let $p$ be a prime. The number of quadratic nonresidues modulo $p^2$, is greater than the number of quadratic residues modulo $p^2$. Is that statement true or false? Why? Thank you.
0
votes
2answers
49 views

Determine amount of congruent numbers

I found the claim in a paper that there are at max 8 integers mod $2^{130}-5$ congruent to one integer mod $2^{128}$. $$u \pmod {2^{130}-5} \equiv g \pmod {2^{128}} \quad\text{ with }u \in U \quad ...
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 ...
1
vote
1answer
68 views

Maximum order for $x$ in $g^x \equiv 1 \mod {n}$, when n=pq

I am currently trying to learn about the ElGamal Digital Signature scheme. It is based on the discrete logarithm problem, where it is computationally infeasible to find $x$ in $y=g^x \mod{p} $), if ...
1
vote
2answers
117 views

Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :) this is a link to a previous post which quickly ...
1
vote
1answer
412 views

Affine cipher - Modular multiplicative inverse

I want to decrypt an Affine cypher. Definition: a^-1(c-b) a = 5, b = 13 Range: Alphabet (26 letters) Letter to decrypt: K (c = 10) So: = 5^-1(10-13) = 5^-1(-3) I am not sure what do to next. ...
1
vote
1answer
120 views

How to solve exponential format modular equation have the same base

I'm reading the paper of Taher Elgamal whichs talks about his digital signature scheme. For example a user needs to sign a document $m \in [0, p-1]$ where $p$ is a large prime number. His private key ...
4
votes
0answers
53 views

Prove that there are $736$ $2 \times 2$ matrices ($A$) where $A=A^{-1}$ [duplicate]

I'm doing some assignments to teach myself cryptology. I am still at the introductory cryptology level, where a lot of it is discrete mathematics, so I believe - and hope - that it is a somewhat ...
11
votes
5answers
323 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
1
vote
1answer
87 views

Why just 4 square roots given ($x^2 \bmod N$)

Oblivious transfer algorithm's page on Wikipedia claims: The receiver picks a random $x$ modulo $N$ and sends $x^2 \bmod N$ to the sender Note that $\gcd(x,N)=1$ with overwhelming probability, ...
0
votes
2answers
77 views

Why is it safe to assume M < all Ns in Håstad's Broadcast Attack

I am reading the Wikipedia article on Broadcast attack. In the prove, the editor made an assumption that M is less than all N. Why is this assumption safe?
0
votes
2answers
62 views

System of Linear Equations for Congruency

So this is my question: Find all x such that $4x=3 \pmod{21}$, $3x=2 \pmod{20},$ and $7x=3 \pmod{19}$ So I know I have to use chinese remainder theorem and I know how to do it if $x$ didn't have a ...