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)

2
votes
1answer
40 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
72 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
893 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
56 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 ...
-2
votes
2answers
81 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
85 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
70 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
202 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
19 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
135 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
45 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
39 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$. $gcd(33,...
7
votes
0answers
167 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
48 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}= \left[\begin{smallmatrix}\frac{1}{6}&-\...
0
votes
1answer
33 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 ...
2
votes
1answer
48 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
189 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 ...
9
votes
1answer
306 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 $...
4
votes
2answers
121 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
59 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
100 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 $(x-1)^...
2
votes
7answers
135 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
45 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
57 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. ...
3
votes
2answers
103 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
46 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
22 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
28 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 28$...
0
votes
0answers
19 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
65 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
73 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
26 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 N,...
1
vote
0answers
47 views

Solving for $m$ algebraically given $m^e \equiv c_1 \pmod n$ and $(\alpha m+\beta)^e \equiv c_2 \pmod n$

Given $m,n,e,c_1,c_2,\alpha,\beta \in \mathbb{N}$ and the system of congruences: $$ \begin{align} m^e \equiv c_1 &\pmod n &(1)\\ (\alpha m+\beta)^e \equiv c_2 &\pmod n &(2) \end{align} ...
3
votes
1answer
54 views

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics?

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics? I've tried Googling this and haven't found anything. If you've got any other application of ...
3
votes
1answer
68 views

What is a good book on Cryptography with an emphasis on algebraic aspects?

I have heard of the subject "Cryptography" but never looked much into it. But this summer, I thought is the best time to look into the subject and see if it will interest me. In U.G, I did ...
2
votes
0answers
42 views

Computing the order of a divisor in the Jacobian of a hyperelliptic curve.

Given a hyperelliptic curve of genus $g$, of equation $H: y^{2}+h(x)y=f(x)$ and defined over the finite field $\mathbb{K}$, how does one compute the order of a (reduced) divisor defined over $\mathbb{...
1
vote
0answers
21 views

Discrete logarithm problem, existence and parity

Let $p>2$ be a prime number such that $p-1=2^st, s>0,t$ odd. Let $a,d\in \mathbb … {Z}^* /p \mathbb{Z}$ with $\left(\frac{a}{p}\right)=1$ and $\left(\frac{d}{p}\right)=-1$, where $\left(\frac{a}{...
1
vote
1answer
178 views

RSA fixed point

What is the number of RSA fixed points, in other words how many $m$ are there such that $$m^e\equiv m \pmod{n}$$ where $n=pq$, for primes $p,q$. I know that the answer is $(1+\text{gcd}(e^n-1,p-1))\...
0
votes
1answer
33 views

How to calculate an elliptic curve

I need to find an elliptic curve in $F_{19}$ that has $|E(F_{19})|=18$. I am really stuck here. Can anyone help?
1
vote
1answer
116 views

Example of using the Hadamard's matrix to determine the superposition

I've came across those notes for Quantum computation from John Watrous. I am having troubles understanding the last example. We have those two vectors, or if I understood correctly, from now on ...
5
votes
3answers
189 views

Factoring product of two primes from solutions of congruence

The algorithm purposed to play a fair game of heads or tails over the phone given here claims that knowing the four solutions to $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is ...
1
vote
2answers
174 views

Isomorphic encryption or homomorphic encryption?

Many encryption functions are said to be homomorphic: http://en.wikipedia.org/wiki/Homomorphic_encryption As encryption functions are invertible, they can be considered one-to-one and onto on ...
0
votes
1answer
55 views

Diffie Hellman: Subgroup Confinement Attack

how can I solve the following tasks? a) Find all primitive elements of $\mathbb{Z}_{37}$. I guess the only possibility here is to try if the remainder off all elements from 1 to 36 to the power ...