4
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
4
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
2
votes
0answers
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 ...
0
votes
3answers
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.
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
78 views

Problem about primitive root

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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
2
votes
1answer
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 \begin{equation} c \equiv ...
3
votes
2answers
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 ...
0
votes
1answer
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 ?
-2
votes
2answers
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$.
0
votes
1answer
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?
0
votes
0answers
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$ ...
4
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
3answers
287 views

I need help understanding “the inverse”

Towards the bottom of this page. where it says ...
3
votes
1answer
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 ...
2
votes
1answer
389 views

Perfect square modulo $n = pq$

I've been stuck on this problem for a while. Any insights to the problem would be great! We start with $n = pq$, where $p, q$ are distinct odd primes. In addition, $\gcd(a,n) =1$. If $x^2 \equiv a ...
1
vote
1answer
161 views

RSA cryptography Algebra

This is a homework problem I am trying to do. I have done part 2i) as well as 2ii) and know how to do the rest. I am stuck on 2iii) and 2vii). I truly dont know 2vii because it could be some special ...
0
votes
0answers
74 views

entropy of perfect cryptosystems

I am working on the product of two perfect crypto-systems and I need to prove that the product is secure. $$a -- [\text{system}\ 1] -- b -- [\text{system}\ 2] -- c$$ How can I prove that $H(a) = ...
2
votes
2answers
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 ...
0
votes
1answer
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?
7
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
1answer
245 views

How is the Schnorr Signature insecure in the following 2 scenarios:

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
2
votes
2answers
276 views

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$ ...