# Tagged Questions

70 views

### If the same message is sent to Alice and Bob who are using different public keys, how can somoene following the channel find $m$

Alice and Bob are using different public keys, Alice is using ($N_{1,2}$) and Bob ($N_{2,2}$). A message, $m$ is sent to both of them using their RSA systems. It is also true that $N_1$ and $N_2$ are ...
167 views

### coding and decoding message with RSA.

First of all, I know how to solve the following exercise; the problem is that there is no solution. "In RSA, Alice chooses $p=53$, $q=63$, public key ($n=3339, e=13$). When Bob sends the message ...
198 views

### How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

It is given that $p$ is prime number and $a\ge1$ solution so far: $x^{\gcd(a,p-1)} ≡ 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in ...
25 views

### Computing fractions Weierstrass curves and DLP problem

I am preparing for a crypto exam by making an old practise exam. I got stuck on the following assignment. I got this weierstrass curve The curve $y^2 = x^3$ is not an elliptic curve over $F_{71}$ but ...
72 views

### Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
21 views

### Solving a congruence relation equation

I have the following equation: $$n \equiv M^a\mod(b)$$ where n, a, b are integers, and M is unknow. How do i solve this equation to find the M value. Those a and b are public keys of the rsa ...
107 views

### RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
59 views

### Analyzing and decoding ciphertext

I have a worksheet which contains a dozen ciphertexts where the goal is to decrypt the encrypted English sentence(s). No information is given about what the text contains or what cipher methods are ...
30 views

### Part of verifying that the Weil pairing $e_m$ is well-defined.

As part of a homework problem, I need to show that the value of $e_m(P,Q)$ is independent of the choice of a point $S \in E[m] \setminus \{\mathcal{O},P,-Q,P-Q\}$, where $E[m]$ is the collection of ...
154 views

### Cube roots modulo $p$

Let $a$ be a positive integer. Is there any general method of solving equations of the form $$x^3\equiv a$$ modulo $p$, where $p$ is a prime number? Here are two examples: Example 1: In ...
76 views

### Plaintext attacks: affine cipher

Consider an affine cipher with encryption function $e$, key $k=(k_1,k_2)$ and some prime $p$. The encryption function $e$ is defined as $e(m)=k_1m+k_2$ modulo $p$, where $m$ is some message ...
76 views

### ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
72 views

### Relating calculus to RSA and/or prime factorization?

I'm writing a math paper on RSA and it would be nice if it had some calculus in it. Is RSA directly related to calculus in any manner? This can include proving theorems, generating keys, or cracking ...
155 views

### Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
164 views

### Coded language puzzle!! [closed]

Here is a puzzle I can't crack. It goes like this: In a certain coded language MANGO=3/5 ORANGE=2/6 APPLE=1/5 Then, POTATO=?? The answer is 5/6. I would like to know to arrive at the answer.
70 views

### Perfect secrecy of hill cryptosystem

Let $H_{n\times n}$ matrix be a key for Hill cryptosystem over English alphabet. How can be proved that Hill cryptosystem is not perfectly secure? (Assuming that all messages are sent with the same ...
174 views

### Extended Euclidean Algorithm in $GF(2^8)$?

I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended ...
64 views

### Calculation using prime number theorem

Fix a (large) number N and suppose that Bob chooses a random number n in the interval $1/2N ≤ n ≤ 3/2N$. If he repeats this process many times, prove that approximately $1/ ln(N)$ of his numbers will ...
164 views

### Square roots in modular arithmetic [closed]

Suppose $n = pq$ with $p$ and $q$ both primes. Suppose that $\gcd(a, pq) = 1$. Prove that if the equation $x^2 ≡ a \bmod n$ has any solutions, then it has four solutions. Suppose you had a machine ...
78 views

Let p be a prime such that $q = \frac{p − 1}{2}$ is also prime. Suppose that g is an integer satisfying $g \not\equiv \pm 1 \pmod p$ and $g^q \not\equiv 1 \pmod p$. Prove that g is a primitive root ...
121 views

### Primitive Root Theorem

Let $p$ be a prime and let $q$ be a prime that divides $p − 1.$ (a) Let $a \in F_p$ and let $b = a^{\frac{p−1}{q}}$. Prove that either $b = 1$ or else $b$ has order $q.$ (Recall that the order of $b$ ...
331 views

### Extension of Fermat's little theorem with Carmichael numbers

I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this ...
110 views

### Problem related to Chinese Remainder Theorem

I'm not sure if there is a typo in the question or if I am incorrect (will point out as I get to it), but I am given that $a,b,m,n$ are integers with $\gcd(m,n) = 1$ and that c \equiv ...
114 views

### Is $2+5x$ a primitive root in $\mathbb{F}_7[x]/(x^2+1)$?

The question I'm inquiring about is all in the title, but I would be more interested in a few things related to the question which I don't know. I know what a primitive root of $\mathbb{F}_p$ is for ...
103 views

### If sent the same message m to Alice and Bob, how someone who follow the channel can find m ?

Alice has public key (n,ea) and Bob has public key (n,eb) with gcd(ea,eb)=1. If sent the same message m to Alice and Bob, how someone who follow the channel can find m ?
280 views

### RSA: Prove that all messages encrypt to itself [closed]

RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
199 views

### RSA: What message will Alice receive?

In RSA, Alice chooses $p=47$, $q=57$, public key ($n=2679$, $e=11$). When Bob sends the message $m=3$, what is the message that Alice will read?
80 views

### How would I create a birthday attack? (Hash Functions)

I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
431 views

### RSA Encryption with number theory

I have a number theory class but my professor just put the homework about RSA encryption where we have absolutely no clue how to do, here's the two question, help appreciated: a) A word has been ...
269 views

### Diffie-Hellman key exchange public key calculation

I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
199 views

### Expected number of tosses - coin tossing

I have here 2 methods for generating a random number, and I need to calculate the expected number of tosses for each method. In each, we let n = log(N) Ne be the bit-length of N and let ...
317 views

### question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
158 views

### homomorphic encryption

Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another (possibly different) algebraic operation performed on the ...
165 views

### Diagramatic Puzzle

This is the Puzzle: and this is the hint: and the answer seems to be 000111 but I have absolutely no idea how it is done. Can anyonw help me out here? That's the puzzle. There are no other ...
70 views

### Cryptographic Coding

If the word “BRIGHT” is coded as” OCPLKV”, then how will you code the word “SERIAL”? 1) CDKYFG 3) CKDGFY 2) FPYNDN 4)FPNDYN 5) none of these Can someone give me the answer with a little ...
287 views

239 views

### RSA public key cryptosystem

I got stuck on a homework question. If anyone could help me with this certain problem, I would be grateful. I'll state what the problem say and some relevant theorem (i believe) that I used to partly ...
389 views

171 views

### block cipher algorithm

Consider a block cipher algorithm with the properties: - Input, output block length is 64 bits and key size is 56 bits. - Given a key K, the key scheduling requires 2 microseconds. - After the key ...
218 views

### AES Key Scheduler

How do you get the rcon for AES's key scheduler? Where does it come from; is it a constant because it seems to differ?
2k views

### Cracking Playfair code

I need to crack a Playfair encoded text without knowing the keyword. While searching the internet I found a way to do this using a 'shotgun climbing hill' method. Problem is, I can't decide how to ...
340 views

### Breaking RSA in a special case

This is a part of homework assignment, and I am stuck. The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here. Public and private keys are ...
When there is no hash function used, $s = k-x \cdot m \mod {q}$ instead of $s = k-x \cdot H(m||r) \mod{q}$? When a hash function is defined as $H(m)$ instead of $H(m||r)$? Ref: Schnorr Signature
### Why is hash function $h$ ($h(w_1 \oplus w_2) = h(w_1) \oplus h(w_2)$) not good?
Suppose $h$ is a hash function, $h$ : { 0, 1 } * $\rightarrow$ { 0, 1 } n and for all $w_1$, $w_2$ it holds: $h(w_1 \oplus w_2) = h(w_1) \oplus h(w_2)$. $\oplus$ is the XOR operation. Why isn't $h$ ...