Tagged Questions
0
votes
1answer
19 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
51 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 ...
0
votes
0answers
35 views
How do I find $m^q\pmod p$ if I already have the following values
I have $g^k\pmod p$, $m\cdot h^k\pmod p$. I also know that $g$ is ìn the set $\{1, 2, \cdots, p-1\}$ and $g$ is of order $q$, so I believe that means that $g^q = 1\pmod p \Rightarrow 1 = g^q\pmod p$. ...
1
vote
1answer
31 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
45 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
193 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
56 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
50 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
45 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 ...
2
votes
1answer
67 views
System of Linear Equations using Mod
I just want to check that I did a certain problem correctly. This is it:
$$a+b=3 \pmod{26}\\2a+b=7 \pmod{26}$$
Solve for $a$ and $b$
Now I setup the augmented matrix:
$$\left[ \begin{array}{ccc}
1 ...
1
vote
0answers
125 views
How to proof this equation without calculating the values it self
I have the following equation.
$$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$
This is part of the AKS algorithm.
The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...
1
vote
2answers
195 views
Solving $4$ simultaneous linear equations modulo $26$
I'm trying to solve these equations to solve a ciphertext which is encrypted by the Hill Cipher. I tried to solve these equations algebraically. (First choose two of them and try to eliminate one ...
1
vote
1answer
116 views
doing an attack on elgamal using pycrypto, how do i solve for this random K? [closed]
I am working on a cryptography homework, doing an elgamal attack. I am using pycrypto's package.
$(a, b) = encrypt(plaintext, K)$
where
$a = g^K \bmod p$
$b = (M * (y^k \bmod p)) \bmod p$
note* ...
0
votes
1answer
146 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 + ...
0
votes
0answers
324 views
Hill cipher known-plaintext attack with unknown alphabet
I'm trying to understand a cryptanalysis of a variant of the Hill cipher using an unkown alphabet through a known-plaintext attack.
The classic Hill cipher use an $n\times n$ inversible matrix
$K
...
0
votes
2answers
51 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 ...
0
votes
2answers
103 views
Need help with finding matrix inverse in $\mathbb{Z}/26\mathbb{Z}$
I am trying to learn the Hill Cipher and I am facing difficulties understanding how to find the inverse of a matrix in Modulo 26. What I've learnt so far is that I need to apply elementary row ...
1
vote
2answers
151 views
Power computation in modulo
I have a confusion regarding power computation in modular arithmetic
Lets say I want to compute
$(7^5)^4 \pmod {17}$
there are many ways to compute this and I get different answers with each ...
11
votes
1answer
7k views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
1
vote
1answer
299 views
RSA Decryption of a huge cipher text and exponent
I am trying to work an assignment question I have been stuck on for some time.
The question is to decrypt the message with given decryption key and mod $n$.
$$374484638351^{320986308343} \bmod ...
0
votes
3answers
583 views
How to calclulate multiplicative inverse of e mod $\phi(n)$?
In this wikipedia article about RSA, At step 5, How are they calclulating value of $d$? Can anybody give me a step-by-step explanation?
Compute $d$, the modular multiplicative inverse of $e ...
0
votes
2answers
81 views
modular cipher proof
the above is a textbook question I found and believe it is very similar to what I have except n=1 mod p-1 and that remainder 1 is something I dont have in my question...
I am terrible at proofs but ...
2
votes
1answer
258 views
Question about finding the nth root in a modulus.
Some notation:
$\mathbb Z_n$ denotes the set of integers up to n i.e. $\mathbb Z_n=\{i│i ∈ \mathbb Z,0≤i < n \}$.
$\mathbb Z_n^*$ denotes invertible elements of $\mathbb Z_n$ i.e. $\mathbb ...
1
vote
0answers
49 views
Finding the random $r$ in a Paillier encrypted message with knowledge of the private key.
In the Paillier cryptosystem, suppose that I know a Ciphertext encrypted with some unknown random $r$ i.e.
$$C = (g^m r^n) \bmod n^2 $$
I know $g, n$, the prime factorization of $n$, i.e., $pq$. I ...
1
vote
1answer
147 views
Multiplicative inverse trouble in RSA Wikipedia entry
I'm having a bit of trouble working through an example in the RSA entry on Wikipedia.
At step 5, $d$ is calculated as $2753$. However, $d$, which is the multiplicative inverse of $e$, can be ...
4
votes
2answers
144 views
Diffie–Hellman Problem
I've been reading the Wikipedia Article on the Diffie–Hellman Problem and I've been wondering whether I understood it correctly, because if I did it seems fairly easy to solve.
The Diffie–Hellman ...
1
vote
1answer
241 views
Breaking RSA in a special case
This is a part of homework assignment, and I am stuck.
The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here.
Public and private keys are ...
0
votes
2answers
5k views
Calculator model with mod function?
I'm wondering does anyone know of a scientific calculator with a mod function?
In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
1
vote
0answers
484 views
Solving Diffie–Hellman problem for low primitive root
What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)?
Of course you could brute force it but I'm interested in ...
