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
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
50 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
21 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
40 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
68 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
102 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
33 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
47 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
29 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 ...
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
138 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
29 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
144 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
265 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
20 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
157 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
44 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
92 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
138 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 & ...
0
votes
0answers
38 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
258 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
59 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 ...
2
votes
1answer
135 views

Solve for $x$ in elliptic curve $y^2 = x^3 + ax + b$

Given $y$, is it possible to solve for $x$ in the elliptic curve equation $y^2 = x^3 + ax + b$ over a finite field? Or is it known to be as difficult as say, something like the discrete logarithm ...
2
votes
1answer
39 views

How to find the next higher combination out of a fixed group of digits?

I have a group of contiguous digits ordered from smallest to highest: 1234. I want a formula (in case it exists) to find the next closer higher combination of the same digits. In this example the next ...
0
votes
0answers
54 views

Questions about RSA cryptosystem primitives: key construction and signature

i) Construct a pair of private/public key RSA, where the prime numbers that you will use are $p=11$ and $q=13$ ii) Describe how the owner of the above keys calculates a signature RSA in the message ...
0
votes
0answers
71 views

ElGamal signature for finding the private key

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$.To ...
5
votes
3answers
871 views

Which background is more suitable to study “Cryptography” [closed]

I am a student of Pure Mathematics and also interested in programming .I have learnt C++,SAGE . Recently I have started learning "Cryptography" .But there are many definitions involved here like ...
-3
votes
1answer
70 views

Rabin-Miller compositeness

Find a witness Rabin-Miller of compositeness of $n=25$ Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller
0
votes
0answers
41 views

Exponential cryptosystem

The cryptosystem works as follows: The plaintext message is first replaced by ciphers (a=00, b=01, etc.) and then encrypted in blocks of four digits. So if the message is "hi", the plaintext number ...
2
votes
0answers
52 views

The odyssey of spies: Kryptos

The part four $K4$ of Sanborn sculpture, a sculpture located on the grounds of the CIA in Langley remains unsolved. As you can read in [1], Sanborn released a clue for the 64th-69th letters in part ...
1
vote
0answers
26 views

What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$. Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is ...
0
votes
1answer
79 views

How should one go about deciphering “ZPLKKWL MFUPP UFL XA EUXMFLP”? [closed]

The Princeton companion to mathematics says, "it is just possible to work out the meaning of the above example by matching letter patterns to those commonly seen in English, but it is quite ...