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)

1
vote
0answers
24 views

Factoring of composite numbers of two primes

Let n=pq, with primes $p=x^a +1$ and $q=x^b+1$, for $x$, $a$, $b$ integers with $a$ not equal to $b$. Is $n$ hard to factor? If not what would be an algorithm and its complexity?
3
votes
1answer
38 views

Why is the discrete log problem intractable?

I have read the other questions on SE on this subject and they were not helpful to me, partially because I am not familiar with advanced mathematical notation. Let me explain the way I'm thinking of ...
0
votes
1answer
21 views

Perfect secrecy of affine cipher

How can I show that the affine cipher has perfect secrecy if the key $(k,a)$, where $k\in\{1,3,5,7,9,11,15,17,19,21,23,25\}$? I know to show perfect secrecy I need to show that ...
1
vote
4answers
45 views

Inverting Modular Exponentiation

How can I go about solving the equation $4 = y^4 \bmod{7}$? Do I have to try all of the possible $y$'s in between $1$ and $7-2$ or is there a smarter way that can be generalized for larger numbers?
0
votes
0answers
115 views

Markov Chain and cryptanalysis

Where I will be able to found papers to read the state-art of the use that Markov chain in cryptanalysis. I found this Canteaut, A. and Chabaud, F. (1998). A new algorithm for finding ...
0
votes
0answers
28 views

maximum number of homogeneous linearly independent equation over $\mathbb{F}_{2^m}$

In Field $\mathbb{F}_{256}$ we are given homogeneous equations in 255 variables from the field. It is said that maximum number of linearly independent such equations we can get are 247. Why ? To be ...
0
votes
0answers
32 views

How do I find the multiplicative inverse of a finite field polynomial using Euclidean Algorithm?

How would I use the Extended Euclidean Algorithm to find a multiplicative inverse of a polynomial in a Galois/Finite field...say, for example, $GF(2^3)$ ? Is it the same process as how it's ...
0
votes
1answer
69 views
3
votes
1answer
35 views

Explanation of this modular arithmetic example in “Understanding Cryptography”

Nothing is more frustrating than a book example that doesn't seem to make sense. I have been tasked to make an elliptical encryption accelerator, and it seemed prudent to read a book on cryptography, ...
1
vote
1answer
42 views

Solving $x^e =c$ in $\mathbb{F}_{p}$

Find all solutions to the equation $x^3=7$ in $\mathbb{F}_{13},\mathbb{F}_{19}$ and $\mathbb{F}_{35}$. In An Introduction to Mathematical Cryptography (Hoffstein et al), we have that proposition ...
0
votes
1answer
44 views

Digital Signature Algorithm (DSA) intuition and its relation to RSA

I already understands how to use the RSA algorithm to sign messages, as you can see in this post of mine. Searching about elliptic curves, I found a general algorithm called Digital Signing Algorithm. ...
2
votes
0answers
34 views

How Do Computers Factor Semi-Primes [closed]

How do computers factor large semi-primes? I know it's difficult but what process do they use? Is it simply a matter of dividing by all odd numbers under the square root of the semi-prime till they ...
0
votes
1answer
22 views

Special-purpose hash functions

I am trying to create a special purpose hash function that will have as few collisions as possible. $99\%$ of the input will be sequential numbers, from $1$ to $N$. The size of the hash table will be ...
29
votes
3answers
18k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...
0
votes
1answer
29 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
27 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
353 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
26 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
2answers
31 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
19 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
41 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
35 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
59 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
27 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
54 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
100 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
17 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
64 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 + ...
3
votes
0answers
64 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 ...
0
votes
0answers
32 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
111 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, ...
2
votes
1answer
41 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 ...
4
votes
2answers
58 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
18 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
24 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
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
57 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
124 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
28 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
33 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
82 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
459 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
30 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
14 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
61 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
101 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
130 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) ...