# Tagged Questions

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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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, ...
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?
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 ...
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 ...
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 ...
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 ...
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* ...
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 + ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 65, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9258318543434143, "perplexity_flag": "middle"}