Tagged Questions
3
votes
1answer
55 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
39 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
39 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
25 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
58 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
36 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
37 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
197 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
59 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
54 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
46 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
73 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
128 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
206 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
134 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
151 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
334 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
52 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
108 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
160 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
8k 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
302 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
621 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
82 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
263 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
51 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
151 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
146 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
253 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
492 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 ...
