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
1answer
27 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
18 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
0answers
21 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
26 views

Decode the text using a 3×3 Hill Cipher [closed]

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
12 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
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?
0
votes
1answer
31 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
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 ...
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
38 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 + ...
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 ...
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
2answers
96 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, ...
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 ...
1
vote
1answer
33 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
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 ...
0
votes
1answer
20 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 ...
1
vote
1answer
39 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 ...
1
vote
1answer
21 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
56 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 ...
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 ...
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)$ ...
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.
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
60 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
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 ...
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: ...
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
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) ...
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 ...
-1
votes
3answers
47 views

How do you find the inverse of $17x + 2$, to decode? [closed]

Let's say I'm trying to encode "hi". "h" is $7$ and "i" is $8$. To encode it you do $17(7) + 2 = 119 \pmod {26} = 15$ which is "p", $17(8) + 2 = 138 \pmod {26} = 8$ which is "i". Thus "hi" becomes ...
1
vote
0answers
26 views

Why does RSA fail when p=q [duplicate]

A lot of questions about this have unsatisfying answers that either argues how unsafe RSA is when $p=q$ or points out that $\phi(n) \neq (p-1)(q-1)$ for $p=q$. However, I'd like to know why the RSA ...
2
votes
1answer
39 views

Extended Josephus permutations generated by keyword

The (well known) generalized Josephus algorithm consists in starting from the ordered set $Z_n=\{1,2,...,n\}$, and choosing and removing cyclically from left to right each m-th element until the set ...
2
votes
2answers
75 views

Miller-Rabin primality test for $2^{32}+1$

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test? I can't find a solution which verify the hypothesis of theorem.
1
vote
0answers
26 views

Why is this prime a bad choice for the ElGamal cryptosystem?

Using the ElGamal cryptosystem in $\mathbb{Z}_{p}^{\times}$, the proposed prime is $p = 2^{1947}\cdot 5 + 1$. The exercise asks me to show why this is a poor choice, and I can't quite do it. In my ...
0
votes
1answer
35 views

Struggling to understand argument about number of roots of a polynomial over a field

On a previous Cryptography exam I'm working through, there is the following problem: Given $$f(x) = x^{134}+x^{127}+x^{7}+1$$ and the field $\mathbb{F}_{2^{n}}$ where $n=1463$, how many roots does ...
0
votes
0answers
55 views

Group of order $n=pq$

Let $G$ be a group of order $n=pq$, where $p$ and $q$ are prime numbers and let $x$ $\in$ $G$. My question is how hard is to compute $x^{-1}$ in $G$ ?
0
votes
0answers
32 views

Direct sum of two points on an elliptic curve

Given $E:y^{2} = x^{3}+9x$ over $\mathbb{Z}_{71}$, and $A = (0,0), \: B = (1,9)$, I'm asked to find $C=A\oplus B$. I just don't know how the direct sum of two points on an elliptic curve is defined, ...
0
votes
0answers
28 views

Zeta function of $y^2 = x^3 - x$ over Fp

Zeta function of $y^2 = x^3 - x$ over Fp, where p = 3(mod 4) Can someone give an explanation of a zeta function? I've tried researching it, and I cannot seem to understand. Is there some kind of ...
0
votes
0answers
9 views

Application of fixed point theory in cryptography

Does fixed point theory has an application in Cryptography? I really don't know about Cryptography. If you mention any books on this matter it really helpful
1
vote
1answer
18 views

Proof that the group of non-generators in a multiplicative group with a prime order is a sub-group

I'm trying to solve the following problem - Let $\mathbb{Z}^{*}_p$ be a multiplicative group such that $p=2^k+1$ and is prime. I need to prove that the set of elements that are non-generators in ...