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

learn more… | top users | synonyms (2)

-3
votes
1answer
31 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
24 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
8 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
30 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
73 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
286 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
38 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 ...
1
vote
0answers
22 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
68 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
19 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?
1
vote
7answers
99 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
21 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
49 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
62 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 ...
1
vote
1answer
26 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
votes
0answers
21 views

Calculate the discrete logarithm

Calculate the discrete logarithm of $11$ as for the basis $3$ in the group $(\mathbb{Z}/31\mathbb{Z})^{\times}$, using Pohlig-Hellman. We have to find $0 \leq x \leq 30$ such that $11=3^x$, right?? ...
1
vote
0answers
13 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
39 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
23 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
46 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
28 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 ...
1
vote
0answers
34 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
43 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
40 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 ...
1
vote
0answers
21 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
15 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
47 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
29 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
87 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
142 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
42 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
35 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
39 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
35 views

RSA, cipher, Cryptosystem

I genuinely have no idea how to go about solving this, any hints would be helpful
0
votes
1answer
31 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 ...
1
vote
1answer
47 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
51 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
21 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
15 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
26 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
15 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
51 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
46 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
18 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
20 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 ...