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
1answer
32 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
18 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
120 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
31 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
25 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
14 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
128 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
26 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
72 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
23 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
23 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
47 views

Trying to understand a part of the RSA algorithm…

The original paper published mentions this... ...
0
votes
0answers
17 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
43 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: ...
-2
votes
1answer
51 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
24 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
80 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
23 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
27 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
21 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
690 views

Which background is more suitable to study “Cryptography”

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 ...
-1
votes
1answer
25 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
29 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
30 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
17 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
73 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 ...
0
votes
2answers
53 views

How to learn cryptography [duplicate]

I have just started learning Cryptography.I looked on the Wikipedia and found topics like "Public key Cryptosystem","Symmetric Cryptography" ,"Cryptanalysis" etc. Below this in the reference section ...
2
votes
1answer
72 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
2
votes
0answers
51 views

Cryptosystem ElGamal

If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal ...
2
votes
1answer
49 views

Probability of collision with a hashing function

I have a data set with N = 80,000 supposedly unique individuals. Individuals are coded by a 9 digit hexadecimal "hashed" version of their 9 digit decimal US SSN. I have no idea what the "hashing" ...
0
votes
0answers
16 views

Framing a lattice problem from information available on multiple runs of GLV decomposition

I have posted a similar question here. The GLV method [ref] is used to speed up ECDSA signature generation. In this method, an input scalar $k$ is decomposed into two scalars, $k_1$ and $k_2$. Then ...
0
votes
2answers
43 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 ...
0
votes
1answer
27 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
0
votes
0answers
33 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. ...
6
votes
0answers
80 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
-3
votes
1answer
36 views

Coding Matrix Problem

(A) Use the coding matrix $A=\left[\begin{smallmatrix}1&3\\5&-3\end{smallmatrix}\right]$ to encode the word jump (B) Using it's Inverse $A^{-1}= ...
0
votes
1answer
28 views

Factor RSA number $n$.

An RSA number $n=p\cdot q$, where $q=2\cdot d +1$, $d$ an odd integer, is given. Assuming $a \in \mathbb{Z}_n$ with $a^4=1$ and $a^2 \neq 1$. How can this information lead to finding $p$ and $q$? I ...
0
votes
0answers
12 views

How to define a one-parameter family of probability distributions

I am trying to evaluate a noise-source as a means of providing entropy to a random number generator. I am running into trouble when it comes to determining the probability distribution that has the ...
2
votes
1answer
33 views

Is the Legendre symbol with respect to a large prime usable as a pseudorandom generator?

Take an output length $\ell$ and a random seed $s \in \Bbb Z_p$ and a large 1000-bit or so prime number $p$ and output the Legendre symbols of $s, s+1, \dotsc, s + \ell - 1$ with respect to $p$. ...
2
votes
3answers
94 views

Chinese remainder theorem - RSA

The following is a excerpt from RSA Decryption correctness proof (section 4) : $$\begin{align} C^d &\equiv M\pmod {p} \tag{1}\\ C^d &\equiv M\pmod {q} \tag{2} \end{align}$$ Now by the ...
7
votes
1answer
294 views

Sum of product with primes

Let $b=e_1e_2,\ldots,e_n$ and $b'=e'_1e'_2,\ldots,e'_n$ be two distinct bit strings of equal length $n$ with same number of occurrences of zeros and ones. The bit string $b$ and $b'$ also must have ...
3
votes
2answers
57 views

Cryptarithm - Interesting Math Problem

This is a very interesting cryptarithm that I came across in an old textbook of mine. It is named accordingly as a tribute to the late Bob Marley (singer). Cryptarithm - Tribute to Bob Marley In the ...
2
votes
1answer
40 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
0
votes
1answer
77 views

Foolproof primality test

I just happened to hear about a prime number test which works 100% of the cases in an university lesson about cryptography. It should be something like: if $p$ divides every coefficient of ...
0
votes
0answers
22 views

How do I construct the S boxes of the following boolean function?

$f(z) = \dfrac{az+b}{cz+d}$ Where $ab-cd$ is non zero. I have already constructed the sixteen element Galois field, but how do I use the function to construct the $S$ boxes?
2
votes
7answers
119 views

find the last digit of $347^{61}$

I need help with the question, "find the last digit of $347^{61}$" . I don't know where to start, I know that it requires modulo arithmetic but I can't think where to start, this is all the question ...
0
votes
1answer
40 views

Multiplication modulo $n$

I encountered the following basic encryption scheme while studying MIT OCW's 6.042 course: Exchange a public prime $p$ and a secret prime $k'$. Encryption: Compute $m'=rem(mk, p)$ ...
0
votes
1answer
33 views

RSA signature scheme-Find a valid signature

Construct a pair of private/public key RSA, where the prime numbers that we use are $p=11, q=13$. Describe how we can calculate a RSA signature at the message $m=2$ without using a hash function. ...
0
votes
0answers
67 views

How can we find the private key?

Alice uses the ElGamal signature scheme with the variables $p=47$, $q=23$ and $g=2$. For two different messages $m_1, m_2$ with $h(m_1)=4, h(m_2)=3$ she produces the signatures $(r_1, s_1)=(14, 8)$ ...
3
votes
2answers
70 views

RSA signature system

Alice wants to construct a RSA signature system to sign messages. The system is secure if the measure $n$ is a product of two primes, each of them has two digits. Describe the ...