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
1answer
51 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
69 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
89 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
40 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
20 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
22 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
61 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
29 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
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
57 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
52 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 ...
1
vote
0answers
44 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
52 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 ...
2
votes
0answers
57 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
37 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 ...
1
vote
0answers
20 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 ...
1
vote
1answer
123 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 ...
0
votes
1answer
30 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
109 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
173 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
1answer
100 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
50 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 ...
1
vote
1answer
61 views

Generator of the unit group

I am required to find a generator of the unit group of $\mathbb{F}_{125}=\mathbb{F}_5[x]/(p(x))$, where $p(x)\in\mathbb{F}_5[x]$ is the irreducible polynomial $p(x)=x^3+x+1$. Does someone know how to ...
0
votes
1answer
19 views

Hil 2-cipher with 26 letter alphabet

A Hil 2-cipher with a 26-letter alphabet $A=1, B=2, \dots, Y=25, Z=0$ has enciphering matrix $A = \begin{bmatrix}19 & 13 \\ 6 & 3\end{bmatrix}$ Questions Verify that $A$ is ...
2
votes
1answer
42 views

RSA, cipher, Cryptosystem

I genuinely have no idea how to go about solving this, any hints would be helpful
0
votes
1answer
34 views

Digital Signatures using RSA

RSA can be used for digital signatures this way: B creates $m$ (product of two primes), $r$ (a number for what gcd($r$, $\Phi(m)$ equals 1) and tells $m$ and $r$ A. B chooses $s$ which is the ...
2
votes
1answer
67 views

modulo RSA decrypt question

Given the following RSA generated public key: $P(3, 55)$. Which integer value should be chosen for $d$ to decrypt messages encrypted with $P$? Check your answer with $M = 8$ and $C = 17$. ...
3
votes
1answer
90 views

RSA cryptography?

I understand how RSA cryptosystem works; however, I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be equal to the product of two distinct, ...
1
vote
0answers
29 views

cryptographic hash functions

Suppose $ℎ: 𝑋\to 𝑌$ is a hash function. For any $𝑦\in 𝑌$ , let $ℎ^{−1}(𝑦)=\{𝑥:ℎ(𝑥)=𝑦\}$ and denote $𝑠𝑦=|ℎ^{−1}(𝑦)|$. Define $𝑁=|\{\{𝑥_1,𝑥_2\}:ℎ(𝑥_1)=ℎ(𝑥_2)\}|$. Note that N counts the ...
1
vote
0answers
16 views

Proposed two key cryptography

Q1. I do not understand why e should be public? It may be more secure to keep it private and known only to the sender and receiver. Q2. I need comments on the following proposed algorithm: Both ...
0
votes
1answer
31 views

Question involving DES cryptosystem

This is probably an easy question. Im Assuming whoever can answer this has access to S-boxes and P boxes etc. Suppose the input to a round of DES is $1010101010......10101010$. (64 bits) Suppose ...
0
votes
0answers
21 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
2
votes
1answer
62 views

How do I find nine messages which are unchanged by RSA encryption using the public key $(3869, 3)$.

I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be the product of two distinct unknown odd prime ...
2
votes
1answer
86 views

Topics in elliptic curves over finite fields

First of all, sorry if I didn't put this question in the correct category. This a paper aimed for undergraduate math majors. So I am writing a general paper explaining about elliptic curves over ...
0
votes
0answers
29 views

Problem with DES Encryption

If the input string to a round of DES is 11001100 · · · 1100 = ‘1100 × 16′ and if the round key is 1111 . . . 111 (‘1 × 48′), Then how can I calculate the 20th and 33rd output bits ? This was an ...
2
votes
0answers
59 views

question based RSA Algorithm

The RSA system was used to encrypt the message M into the cipher-text C = 6. The public key is given by n = p q = 187 and e = 107. In the following, we will try to crack the system and to determine ...
2
votes
1answer
63 views

What are some good resources to study Cryptography?

What are some good resources to study Cryptography? I have knowledge of abstract algebra .Is it enough to take up Cryptography as a special paper or I will have to undergo courses in some other ...
0
votes
0answers
28 views

Decryption of RSA

I am given the following information about an RSA-encryption: $e=31671865305320609$ (public key) and $n=10e+3$. Then I am given the ciphertext $c$ which I omit here due to his length. The task is to ...
0
votes
1answer
97 views

Math behind perfect hash

I am reading material on cryptographic hash functions and it says "Collision resistant property : for a hash of length L, a perfect hash would take $2^{L/2}$ attempts." Can someone explain why? ...
0
votes
0answers
122 views

How to decrypt a ciphertext by using the mutual index of coincidence?

I am trying to decrypt a Vigenére cipher text. I have found the key length by computing Index of Coincidence of substrings. The key length is 12. I know the letter frequencies the string and the ...
19
votes
3answers
4k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 ...
1
vote
1answer
361 views

How is de = 1 (mod ϕ(n)) calculated

I am reading RSA algorithm. So, I was writing a question but I saw this question and still couldn't understand it. If $$e\cdot d \equiv 1 \pmod{\varphi(n)},$$ then $$ed=k\cdot \varphi(n)+1, \qquad ...
1
vote
2answers
47 views

Proof DES is injective - is this a valid argument

Without going too much into detail into the crpytography of the matter since not every mathematician is interested or knowledgable in the field, there is an encryption process called DES (data ...
0
votes
0answers
22 views

What is the proper way to generate a key in Merkle-Hellman Knapshack Cryptosystem?

This article says that, if a message is 8-bit, then there should be 8 elements in the Super Increasing Sequence. ...
1
vote
1answer
69 views

Is it possible to estimate the number of primes between 0 and a 128 bit number?

I'm attempting to visualize an RSA public/private key pair, or a SHA2 hash. In order to reduce that massive number that is meaningful to humans I'm looking at this SHA2 visualization function to ...
72
votes
6answers
8k views

Mathematically, why was the Enigma machine so hard to crack?

Mathematically, why was the Enigma machine so hard to crack? In laymen terms, what was it exactly that made cracking the Enigma machine such a formidable task? Everything I have seen about the ...
0
votes
2answers
49 views

Calculating all Possible Keys vs All possible numbers confusion

With a key of length n bits, there are 2n possible keys. eg: 128-bit key length will have 2128 possible keys But when calculating every possible n digit number, ...
5
votes
1answer
200 views

How fast was the Turing's machine for breaking the enigma code?

We know that, recently, personal computers make around $10^9$ calculations per second, and I'm just curious about how many calculations was able to compute the machine invented by Turing for breaking ...
0
votes
0answers
54 views

how to calculate number of points on an Elliptic curve over prime field? suggest any best method

$y^2=x^3+a*x+b\pmod p$. For this elliptic curve over prime field, how to calculate number of points lies on the curve? suggest any best method.