# Tagged Questions

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

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 ...
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, ...
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 ...
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 ...
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$?
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$ ...
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 ...
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,......
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 ...
1answer
154 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
0answers
9 views

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 ...
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 ...
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, ...
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 ...
1answer
25 views

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, ...
1answer
30 views

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 ...
2answers
49 views

### Trying to understand a part of the RSA algorithm…

The original paper published mentions this... ...
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 ...
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: ...
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}$. ...
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 ...