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
33 views

How can I explain a Zero Knowledge Proof with minimal mathematics

I asked this earlier on how to explain a Zero Knowledge Proof to a layman. but I'm looking for a mathematical analogy that might "enhance" the superpower explanation. In that linked superpower, that ...
0
votes
0answers
26 views

Attack El Gamal private key when p is composite

I'm supposed to find private key of El Gamal cypher. I have public key ($p,g,h$) and order of the element g ($q$). $$h = g^x\ mod\ p$$ ($x$ = private key) I have figured out that $p$ is composite, ...
0
votes
1answer
79 views

An encoding of non - empty sequence of strings

An exercise problem $:$ Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote ...
1
vote
3answers
50 views

Use Fermat's Little Theorem to prove $24^{31} \equiv 23^{32} \mod{19}$

I'm trying to prove $24^{31} \equiv_{19} 23^{32}$. All I have so far is that this is equivalent to $23^5 \equiv_{19} 24^6$ by multiplying both sides by $24^623^5$. I can see that there seems to be ...
-1
votes
1answer
41 views

What's the maximal number of q-arrays of $A_7(7,d)?$

$ A_q(n, d) $ is the maximum number of a $q$-arrays of length n and minimum distance at least d. What's the best known exact values of $ A_7(7,d)$ for $d=1$ to $7$?
5
votes
1answer
77 views

pseudo-primality and test of Solovay-Strassen

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and : $$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$ Euler's criterion states that if $n$ ...
0
votes
2answers
51 views

Cryptography: Solve x² ≡ 331 (mod 385) using congruencies

How can I find (3) congruence equations to solve $$x^2\equiv331\pmod{385}$$ using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to ...
0
votes
0answers
33 views

Finding generator for El Gamal cryptosystem

I am working with the prime p = 503 I know about the algorithm where you find the factors of (p-1), which in this case are 1,2,251 and 502. Then i tried to randomly select an integer from g ={1,2,......
3
votes
2answers
108 views

Understanding Carmichael Number

A Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$a^{n-1} \equiv 1 \pmod n$$ $\forall a \in \mathbb Z_n$ such that $\gcd(a, n) = 1$ Wiki says ...
2
votes
1answer
154 views

RSA when N=pq and p = q

I was curious what's to happen when $p = q$ for $N=pq$ in RSA scheme. First I realize that one can easily find out $p$ and $q$ by taking a square root of $n$. However, it appears to me that under $\...
0
votes
0answers
11 views

Determine if an algorithm has solutions or not

I m actually studying Turing works concerning Enigma's machine. Actually, I am wondering if it does exist anything, an algorithm or something that allows people to tlel if an algorithm can be break ...
5
votes
2answers
60 views

Find element with order 12 of multiplicative group using CRT

I have been stuck on this question for a long time and don't really understand how the Chinese remainder the is related to the order of a unit. Use the Chinese Remainder Theorem to find an element ...
0
votes
0answers
53 views

What is the advantage or disadvantage of Pollards rho algorithm compare to Parallel Substitution or Quantum Algorithm?

I’m trying to combine the two algorithms but for the mean time I want to know your opinion or suggestion. I use my spare time to create a Pollards rho algorithm using basic formula in spreadsheet to ...
0
votes
1answer
22 views

Question related to the security of RSA method

I learned about the RSA method, where if B wants to send a message $M$, say $0 \leq M <n = pq$ to A with public key $(n,e)$, then B sends $M'= M^e (mod \ n)$. Then A can decode this message using ...
0
votes
1answer
41 views

Understanding Quadratic Residue Modulo n Structure

Quadratic Residue Modulo n: $a \in \mathbb Z_n^*$ is quadatic residue of modulo n if there exists an element $x \in \mathbb Z_n^*$ such that $$x^2 \equiv a \mod n$$ I'm not getting the intuition ...
0
votes
1answer
29 views

cWhat is the importance of Multiplicative Group in Number Theory

I'm studying Number theory basics for Cryptography Course. There is a term called Multiplicative Group which confuses me litle bit I know $|\mathbb Z_n^*| = \phi(n)$ (Euler Phi Function) and $\...
3
votes
0answers
74 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 ...
2
votes
2answers
114 views

Solving a cubic congruence equation with Chinese Remainder Theorem

I have the following congruence equation: $x^{3} \equiv 3 \bmod(357035)$ which I'm having troubles solving. The prime factorisation of $35705$ is $5\cdot 7 \cdot 101^{2}$. I thought I would solve the ...
0
votes
1answer
34 views

Select two distinct primes each with 6 binary digits and use them to design an RSA cryptosystem.

Describe how to design an RSA cryptosystem based on primes p = 13 and q = 7. That is, propose the public key and the private key. Encode the message 100101 and then decode it. I'm mimicking my ...
0
votes
1answer
88 views

Adding points on an elliptic curve

I'm trying to work out a problem from a previous exam in Cryptography regarding elliptic curves. I can add points on an EC using the formulas given, but the suggested solution to this exam problem I ...
0
votes
0answers
22 views

Decode the following message which was sent using mod $m=7081$ and exponent $k=1789$ [duplicate]

Decode the following message which was sent using mod $m=7081$ and exponent $k=1789$ (RSA). $(5192, 2604, 4222)$ I understand this question has already been asked the the solution was never posted ...
0
votes
0answers
48 views

Finding number of points on elliptic curve

I'm working on a previous exam problem, and my solution does not match with the given one, and I don't know why. I have the elliptic curve $$E: Y^{2} = X^{3} + X + 46$$ over $\mathbb{F_{101}}$. We're ...
1
vote
0answers
17 views

Suggestion for a book on cryptography [duplicate]

Can someone suggest me a good book on cryptography with a lot of solved examples.
2
votes
1answer
25 views

Extracting secret key - d of RSA

I need to prove that if John can ask Alice to sign any messages, John will eventually figure out secret key "d" and decrypt all Alice's messages. How do I go about proving that. Any hint will be ...
0
votes
0answers
9 views

Elgamal cryptograph for finding message $αm^ν$

Alice uses an ELgamal cryptography system with base the group $Z^*_p$ and parameter(generator of group) the $g$.You know the $p,g$ and the public key of Alice $y$.Still,you are given the cryptograph $(...
2
votes
0answers
30 views

If $g \in \mathbb{Z}/p\mathbb{Z}$ has prime order $q$, how well-distributed are the powers of $g$ modulo $q$?

More precisely: the powers of $g$, when identified with coset representatives from $\{1,\cdots,p-1\}$, consists of $q$ distinct integers. If these integers are all reduced modulo $q$ to the set $\{0,1,...
6
votes
1answer
79 views

ElGamal signatures and “related randomness”

As part of a security CTF competition, the following variation of the ElGamal signature scheme had to be broken: Let $q$ be prime and $p = 2q + 1$ also prime. In practice these two primes were ...
0
votes
2answers
151 views

Playing rock paper scissors over online chat.

Is there a way to play rock, paper and scissors fairly over internet chat? By this, I mean that both players cannot play their hands simultaneously, one of them has to go first and the second player ...
0
votes
1answer
32 views

cartographic RSA algorithm

I am a programmer, While I was studying the RSA encryption I found some difficulties with some mathematical matters RSA algorithm has the following concepts Modulo, Modular multiplicative inverse, ...
0
votes
0answers
23 views

Question about Affine Cipher and it's key.

We have a key = (a, b). An element a and the modulus must be relatively prime for the inverse of a to exist (which we need for decryption). If we have 29 letters in our alphabet, how can I determine ...
1
vote
1answer
25 views

Modular arithmetic with different moduli?

I am stuck on a problem involving numbers being reduced by two different moduli. Assume I have the following two numbers $g_1$ and $g_2$: $g_1 = (2^{1024} \mod(p)) \mod(q)\\ g_2 = (2^{1234} \mod(p)) \...
0
votes
1answer
28 views

Prove entropy theorem

Doing a course of cryptography I have been asked to prove the following: $H(X,Y) = H(Y) +H(X|Y)$. But I simply do not know where to start, so a hint in the right direction would be very much ...
1
vote
0answers
27 views

How to expand Diffie-Hellman key exchange for multiple users?

To provide OTR (off the record) security for XMPP group chats we've discussed an idea for a Diffie-Hellman key exchange algorithm for multiple users. It should work as follows: Choose a cyclic group ...
1
vote
0answers
11 views

Efficiency of McEliece Cryptography

Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys. However I have never heard about the size (or length) of its ciphertext. For example, ...
0
votes
1answer
39 views

Security of such cryptosystem design?

Is one able to reveal $m$ when $$С = (m + r)^e \bmod N$$ $C$ is known $r$ is known $e$ is known $N$ is known and not prime
0
votes
0answers
20 views

Converting Walsh coefficients to values of a function

I assume I know the Walsh coefficients of a function f: $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2}$. Is there any efficient possibility to get the values of the function f ?
4
votes
3answers
145 views

Iterated square roots over finite field. When do we hit a nonresidue?

Suppose that we are working within the integers modulo $p$ where $p$ is some odd prime number. Suppose that $x_0$ is a (nonzero) quadratic residue mod $p$ then there exists some $x_1$ such that $x_1^2 ...
1
vote
1answer
289 views

Calculating Shannon Entropy for DNA sequence?

I'm following the formula on http://www.shannonentropy.netmark.pl/calculate to calculate the Shannon Entropy of a string of nucleotides [nt]. Since their are 4 nt, ...
1
vote
1answer
30 views

Anti-symmetric if $AB= 1$ and $BA=0$ but every vertex has loops?

I'm creating a directed graph from an adjacency list. The $0$ present that there is no relation while the $1$ represent that there is. So i have a quick question regarding this. Lets assume that $AB ...
0
votes
0answers
21 views

Type(s) of Hashing function that keeps the ordering information

I am asking this question from a perspective that we need to store a set of hashed data that can be queried later for in an ordered fashion. My situation is that some data has to be encrypted, I am ...
1
vote
2answers
160 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
0
votes
0answers
49 views

How to find the period of a recurrence relation

Given the recurrence relation $s_{i+5}=s_{i+1} + s_i$ over $\mathbb{F}_2$ with initial states $s_0 = 1, s_1 = 1, s_2 = 1, s_3 = 0, s_4 = 1$ What is the best/quickest way to find the period of the ...
1
vote
1answer
93 views

How do you find the smallest legitimate encryption exponent when you are only give a p and q value in a given range?

I have been given this as an assignment question but I'm not sure approach it. EDIT: Sorry I should have added more details. It is a cryptosystem using the RSA scheme. p and q are both old prime ...
-1
votes
1answer
149 views

Finding variables in a 2x2 matrix multiplication

How do I find $b$ and $d$ in the equation: $\begin{bmatrix}6 & 25\\12 & 15\end{bmatrix} \times \begin{bmatrix}2 & b\\5 & d\end{bmatrix}$ = $\begin{bmatrix}22 & 17\\10 & 22\end{...
0
votes
0answers
39 views

Binary solutions of multivariate polynomial system in special (factored) form.

In my personal research I've run into a system of multivariate polynomials (with coefficients in a field). I am aware that there is no polynomial time algorithm (in the number of indeterminates) for ...
1
vote
2answers
49 views

Trying to understand a part of the RSA algorithm…

The original paper published mentions this... ...
0
votes
0answers
273 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
2
votes
1answer
61 views

Finding a path in a graph by its hash value

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$. Question: ...
-3
votes
1answer
70 views

Describe a fast (polynomial time)algorithm who takes as input the elements $g^a,g^b$ and gives as output the element $g^{a \cdot b}$

Let $q$ prime number, $G$ a cyclic group with order $q$ and $g \in G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$. ...
1
vote
2answers
32 views

Algorithm for finding prime numbers of specific form

Given the natural number $n$,who is in the form $p^2 \cdot q^2$,with $p$,$q$ prime numbers.Also $φ(n)$ is given.Describe a fast algorithm(polynomial time) that calculates the $p$ and $q$.Apply your ...