Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers. Consider posting your question at Cryptography.SE.

learn more… | top users | synonyms (2)

0
votes
0answers
10 views

Proofs of congruence relations

Exercise 2.3 from "Introduction to Mathematical Cryptography" Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ of order $r$. (a) Suppose that $x = a$ and $x = b$ are both integer ...
0
votes
1answer
11 views

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26.

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26. I figured that the matrix is only invertible if its determinant and the n value 26 's gcd is 1, meaning they are ...
1
vote
1answer
304 views

Primitive Root Theorem

Let $p$ be a prime and let $q$ be a prime that divides $p − 1.$ (a) Let $a \in F_p$ and let $b = a^{\frac{p−1}{q}}$. Prove that either $b = 1$ or else $b$ has order $q.$ (Recall that the order of $b$ ...
1
vote
0answers
20 views

Find GCD of polynomials over GF(101)

Hello all I'm teaching myself cryptography, and I'm struggling with polynomial arithmetic over finite fields. I've some what been able to teach myself how to do the arithmetic over $GF(2)$, but when ...
0
votes
0answers
24 views

Decode the text using a 3×3 Hill Cipher [on hold]

Decode the text using a 3×3 Hill Cipher NKVCHDGPVZYKHYESCHUWOTRUNKUEXFQDHVJMGIVHNCUYGYKJNXNGWLOKVJRUDYYBGNYCZVHYRFZFDBCSCPFGOTBDLDKOM Given Plaintext - 'theintern' How do I decrypt ?
0
votes
2answers
22 views

RSA Paper Example

I am reading the 1978 paper on RSA Algorithm. There is an example included in the paper and there is a section I can't get my head around. It says: Since $e = 10001$ in binary, the first block ($M ...
0
votes
0answers
11 views

Involutary Keys for Shift Cipher

Let $e_K(x)=(ax+k)\mod m$ and $d_K(x)=a^{-1}(x-k)\mod m$, where $K=(k,a)$ How can I show that $e_K(x)=d_K(x)$ if and only if $k^{-1}=k\mod m$ and $a(k+1)=0\mod m$?
0
votes
1answer
30 views

Proving if a permutation cipher is perfectly secret?

From what I've read, perfect secrecy in its most basic form, that the encrypted text reveals no information about the plaintext, be it structure or content. A permutation cipher is easy for me to ...
0
votes
1answer
33 views

Modular exponentiation and two primes

Given two primes $11$ and $5$, find all $\alpha> 1$ such that $$\alpha^{5} \equiv 1 \pmod{11}$$ What theorem will help me to find it out?
1
vote
1answer
38 views

The fastest Gröbner basis algorithm available?

for my undergraduate thesis I'm (pseudo) replicating algebraic attack on certain cryptosystem using gröbner basis approach. The heart of original attack was F5/2 algorithm (since the cryptosystem is ...
0
votes
1answer
26 views

Equation solution in modular arithmetic

Given two primes $11$ and $5$, find all $α > 1$ such that $α^{5} \equiv 1 \mod 11$. How would you compute that?
1
vote
1answer
52 views

Launching a Plaintext Attack against Affine Cipher

Update 2 Being new to the world of Stack Exchange I did not realize that there exists a site solely devoted to cryptography. In light of this, I hope someone could help me migrate this question to ...
4
votes
2answers
96 views

Who has revealed more about a secret password?

Today, Bob, a colleague of mine, accidentally revealed that his password contains a. Alice laughed, but then also inadvertently said her password does not contain ...
2
votes
1answer
14 views

Decrypting a message using rem()

Hello i have a problem in decrypting a message using this algorithm Beforehand : The sender and receiver agree on a large prime p, which may be made public. (This will be the modulus for all our ...
1
vote
0answers
36 views

Involutory key for the substitution cipher

I need to find all the involutory keys for the substitution cipher over $\mathbb{Z}_7$. I wasn't sure what can be the key for the substitution cipher. For example, for the affine cipher, $e(x) = kx + ...
2
votes
1answer
378 views

Calculating Probabilities for Substitution Ciphers using Frequency Analysis

I have been trying to put together a tool that can take in cipher text encrypted via a simple substitution cipher and calculate the most likely "key" (that is, how the plain text letters were mapped ...
3
votes
0answers
50 views

Why are supersingular elliptic curves useful for cryptography?

I don't know very much about cryptography and would like to learn more. I know the basics of RSA alogrithm and how elliptic curves over finite fields can be used to do something similar. But I would ...
6
votes
1answer
809 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
0
votes
0answers
30 views

Puesudorandom generation

Hi i have created a stream cipher that creates a'random' stream of numbers(1-99) as subkeys for the message.The generation algorithum is as follows:(key mod (iv+counter)) mod 99.The key is the main ...
2
votes
2answers
95 views

What numbers are relatively-prime to $256?$

Given the numbers are in the range $1$ to $256$, which ones AREN'T co-prime, would be an easier question$?$ This question may be very specific and hopefully trivial for somebody on the maths board, ...
1
vote
1answer
32 views

How many times do I loop Solovay--Strassen primality test

First, I am aware of this former thread: math.stackexchange Yet it doesn't answer my question. If I want to check if an integer $n$ is prime using the Solovay--Strassen test, how many times do I ...
0
votes
0answers
20 views

Dirichlet's 1842 Approximation theorem: Does this specific variant of the theorem actually exist?

From this pdf: Theorem (Dirichle,1842) Assume that $\gcd(a, b) = 1$. If $r,s$ are any natural numbers such that $\gcd(r,s) = 1$, and $|\frac{a}{b} − \frac{r}{s}| < \frac{1}{2s^2}$ then ...
0
votes
1answer
37 views

Proving Wiener's attack on RSA: help understanding what is meant by a “classic approximation relation”?

I am researching Wiener's attack on the RSA cryptosystem. The theorem, found here beginning on page 4, is as follows: Let $N=pq$ with $q < p < 2q$. Let $d < \frac{1}{3}N^\frac{1}{4}$. Given ...
4
votes
2answers
47 views

Where do hash functions come from?

I have some basic understanding of how hash functions work, however, I have no idea of how mathematicians created them. Were them a byproduct of a non cryptografics related research or were them a ...
0
votes
1answer
1k views

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
0
votes
1answer
15 views

Diffie-Hellman protocol

So I get the basics of diffie-hellman, discrete logarithms, modular arithmetic etc but I feel like I am missing something substantial or I would not be able to reverse it so easily, unless it is due ...
4
votes
4answers
14k views

Example for Cyclic Groups and Selecting a generator

In Cryptography, I find it commonly mentioned: Let G be cyclic group of Prime order q and with a generator g. Can you please exemplify this with a trivial example please! Thanks.
0
votes
1answer
19 views

Euclid's algorithm to solve (e x d) mod p = 1

I need to use Euclid's algorithm to find d in the following equation. Given values for e and p $$(e\times d)\mod p = 1$$ I have used Euclid's algorithm to find the gcd of two numbers but can't see ...
0
votes
3answers
10k 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
1answer
20 views

Fermat's theorem as primality tester when powers are too large

As part of cryptography, if I wish to test whether a given number is probably prime I use the formula: $$ a^{p-1} \equiv 1 \bmod p $$ where $p$ is (potentially) a prime number. However, when it ...
1
vote
2answers
54 views

Fermat's Theorem as a primality tester doesn't work for all primes?

I'm studying cryptography. According to Fermat's theorem... $$a^{p-1} \pmod p = 1$$ .. when $p$ is a prime number. The above should prove whether a number is prime or not yet it doesn't work for ...
0
votes
2answers
112 views

Reversing Rotation + XOR

I have this cypher which is as follows : Take 2 numbers : A=1011 and B=1010 if the ith bit of X is 1 then shift Y* i times to the left. So in the end you will get ...
2
votes
0answers
25 views

Factor the RSA modulus $n = 3844384501$ knowing that $3117761185^2 \equiv 1 \pmod{n}$

As per the title, the task is to Factor the RSA modulus $n = 3844384501$ knowing that $$3117761185^2 \equiv 1 \pmod{n}\text{.}$$ $n$ being an "RSA modulus" means that it is a product of two ...
0
votes
0answers
31 views

If the hash of the multiplication is equal to the multiplication of the hash, how can this be used to leverage an attack?

Assume a hash function $H:\left\{0,1\right\}^*\to G$ where $G$ is a group and assume that finding an inverse in $G$ is easy. How can a preimage efficiently be found using the fact that $H(M_1\cdot ...
2
votes
2answers
75 views

Involutory matrix $2 \times 2$ [duplicate]

I want to find out how many $2 \times 2$ involutory matrices are there over $\mathbb Z_{26}$. $ $ Is there any formula to calculate this? $ $ Thanks for your help.
11
votes
5answers
453 views

Why are there $736$ matrices $M\in \mathcal M_2(\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 ...
0
votes
0answers
17 views

Is DEHP a kind of Multivariate hard problem?

Please correct me if I am wrong. To my understanding , given a '$m$' multivariate set of equations in '$n$' variables in a integer field '$F$' is hard to solve, even in case of $MQ(multiquadratic)$ ...
0
votes
1answer
27 views

Modular exponentiation commutativity in Diffie-Hellman

I've been learning about Diffie-Hellman key exchange. One of the main tricks comes down to a commutativity property of exponentiation in the relevant modular arithmetic, it seems. Something like: ...
0
votes
0answers
12 views

What is the size of Quotient in integer division with remainder?

Suppose $a=(a_{k-1},\dots,a_1,a_0)_Z$ and $b=(b_{l-1},\dots,b_1,b_0)_Z$ then $ab=m=(m_{k+l-1},\dots,m_1,m_0)_Z$ so $m$ is a $(k+l)$-digit number in the base $Z$. Let $b_{l-1}>0$ and $a=bq+r$ where ...
1
vote
3answers
47 views

Find base of exponentiation

Given the two primes $23$ and $11$, find all integers $\alpha$ such that $\alpha^{11} \equiv 1 \mod 23$. How to compute this? What to use?
2
votes
1answer
90 views

find the structure of an elliptic curve over a finite field

For the elliptic curves E1,E2,E3, and E4 defined below, determine the structure of the groups Ek(F13) by using the information given below together with a minimal amount of extra (hand) ...
1
vote
1answer
87 views

Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^d\equiv1 \pmod n$…

Question: Let $n = pq$ be a product of two distinct odd primes and put $d = \gcd(p − 1, q − 1)$. (a) Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^d\equiv 1 \pmod n$. (b) ...
2
votes
1answer
36 views

the way to calculate the number of element in $\mathbb Z^*_n$ have order 2?

I want to show that if $n=pq$ such that $p$ and $q$ are distinct odd primes the number of $\ (a,b)$ such that $a$ and $b \in \mathbb Z_n$ and $a\equiv a^{-1}\pmod n$ and $b(a+1)\equiv0\pmod n$ is ...
2
votes
2answers
54 views

Why crypto algorithms are primarily based on finite fields?

I want to learn why people use finite fields in cryptography? I mean there are other fields like number fields, function fields that are not finite. There are also some other topological fields, like ...
2
votes
3answers
44 views

What's the general mathematical method to go about solving a substitution cipher?

Here's a question from a professor's page: Decipher the following simple-substitution cryptogram, in which every letter of the message is represented by a number. ...
0
votes
1answer
23 views

Confused about the number of permutations of the Enigma Machine

I recently learned about the Enigma Machine in my cryptography class, but I am a bit confused as to the number of permutations of the wheel settings. According to every article I've read on the ...
2
votes
3answers
157 views

Chinese remainder theorem - RSA

The following is a excerpt from RSA Decryption correctness proof (section 4) : $$\begin{align} C^d &\equiv M\pmod {p} \tag{1}\\ C^d &\equiv M\pmod {q} \tag{2} \end{align}$$ Now by the ...
0
votes
2answers
32 views

$RSA$ cryptosystem with $e=2$

There exists a $RSA$ cryptosystem with $e=2$ , where $e$ is the encryption exponent ?(In general $e>2$)
1
vote
1answer
31 views

RSA Cryptography math problem

I have this math problem I'm kind of stuck on. You intercept the message 27284682555982882069237 which was encrypted using a public modulus of 124137798108168664109413 and an encryption ...
1
vote
1answer
32 views

Galois Field to bits, implementation is fine, but the mathematics is not.

I am working on a hardware implementation of the SIMON cipher and the key expansion is based on GF(2). The original paper is here, https://eprint.iacr.org/2013/404 I have successfully created the ...