Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

learn more… | top users | synonyms (2)

-4
votes
0answers
134 views

My answer isn't matching the key at the bottom. I don't think I encoded it correctly. [on hold]

Raise 10666369614354225120 to 16479139101483902597. Take the result and divide by 18074899840695706733. Take the rest of that division. Encode it to hex (remember, always uppercase!) Add the dashes ...
1
vote
0answers
12 views

Find the ElGamal authentication algorithm of signature $(r,s)$ [on hold]

Let $p$ prime number $q/p-1$ prime and $g\in (Z/pZ)^*$ element of order $q$.Also $a\in \{1,...,q-1\}$ the private key and $y\equiv g^a\pmod p$ the correspoding public key.For each of the following ...
0
votes
0answers
16 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
42 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: ...
0
votes
0answers
23 views

Construction of ElGamal signature [closed]

Alice uses an ElGamal signature in group $(Z/pZ)^*$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in ...
-3
votes
1answer
47 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
23 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
61 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
0answers
12 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
19 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
666 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 ...
-2
votes
1answer
24 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
28 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
19 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
16 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
69 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
47 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
71 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
50 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
41 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
29 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
24 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
74 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
35 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
10 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
84 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
289 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
44 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
37 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
73 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
115 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
36 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
66 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 ...
0
votes
1answer
32 views

ElGamal signature scheme

Alice uses the ElGamal signature scheme in the group $(\mathbb{Z}/p\mathbb{Z})^{\star}$ without the use of a hash function. To sign the message $m \in (\mathbb{Z}/p\mathbb{Z})^{\star}$ she calculates ...
0
votes
1answer
17 views

Show that $(M^{e})^d \equiv M$ (mod n).

I need to show the following. Given $n,e \in \mathbb{Z^+}$ such that $gcd(e,\phi(n)) =1$, let $d$ be an inverse of $e$ (mod $\phi(n)$), and let $M \in \mathbb{Z}$ such that gcd($M,n$) = 1. Show that ...
1
vote
0answers
14 views

Apply Pohling-Hellman to calculate the discrete logarithm

I am looking at the following example of calculating the discrete logarithm with Pohli-Hellman. The group is $\mathbb{F}_{29}^{\times}$ and we given $y=10$ and $g=3$. We want to find $0 \leq x \leq ...
0
votes
0answers
42 views

Pohlig-Hellman algorithm

I am studying Cryptology right now and I am facing some difficulties to understand the Pohlig-Hellman algorithm. Could you explain to me how the algorithm works?? $$$$ EDIT: I read an ...
0
votes
0answers
25 views

How can we find the decrypted message?

Let's suppose that $A$ uses the encryption system of ElGamal with with public key $(p, g, y)=(53, 2, 27)$. $B$ sends to $A$ the encrypted message $(15, 34)$. Find the original message. We have that ...
0
votes
0answers
17 views

What are solid textbooks to learn number theory (for use in cryptography specifically)? [duplicate]

I am an undergraduate looking to have a solid background in number theory before I begin taking courses in modern cryptography. Any recommendations are appreciated!
1
vote
1answer
49 views

hyperelliptic curve

Please help me to solve this question: Let $H$ be a hyperelliptic curve over $\mathbb{F}_{103}$ given by the equation $ y^2 = x^5+1$. let $J$ be the jacobian of $H$ defined over $\mathbb{F}_{103}$. ...
1
vote
2answers
30 views

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
0
votes
0answers
24 views

Does RSA use two one-way functions?

I'm trying to understand the concepts behind RSA right now. From what I've learned so far, it's pretty much all about a one-way function with a trapdoor: Raising the message to the e'th power modulo ...