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

learn more… | top users | synonyms

2
votes
1answer
33 views

Given four numbers $(a,b,e,n)$ is it possible to find $k$ such that $k^{e}a = b \pmod n$?

Let $n$ be a large given number. Also, $n = pq$ for some unknown primes $p,q$. The Euler Totient function, $\varphi(n) = (p-1)(q-1)$ is not known or easy to calculate. $e$ is a given number co-prime ...
1
vote
1answer
19 views

Given three numbers $a, b$, and $n$, is it possible to find a number $k$ such that $ka\equiv b\pmod{n}$?

I came up across this problem working on some (purely academic) attack on cryptographic schemes. Given any three integers $a,b,n$ such that $a<n,b<n$, I am interested in an integer $k$ which ...
2
votes
1answer
94 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
0
votes
1answer
664 views

RSA encryption/decryption scheme

I've been having trouble with RSA encryption and decryption schemes (and mods as well) so I would appreciate some help on this question: Find an e and d pair with e < 6 for the integer n = 91 so ...
1
vote
1answer
72 views

Primality test with polynomial congruence (preliminary to AKS algorithm)

I have trouble in understanding the proof of this primality criterion: $n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$. In ...
2
votes
0answers
164 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 ...
5
votes
3answers
69 views

Public Key Cryptography

Assuming that a message has been sent via the RSA scheme with $p=37$, $q=73$, and $e=5$, what is the decoding of the received message "34?" So far, I have $x^5 \pmod{37\times73} \equiv 34$. How do I ...
0
votes
0answers
10 views

What is the name of the specific kind of involution used in most reciprocal ciphers?

Is there a name for the subset of involution functions used in most reciprocal ciphers? I've been saying things like A pairing is a function f that pairs up each element x with some other element y, ...
1
vote
1answer
113 views

Using euclidean algo to find d (RSA encryption)

The questions says "let p = 5, q =11, n = 55 tocient(n) = 40. e=7. Use the Euclidean algo to find the value of d. This is driving me crazy. Here's what I did: ...
0
votes
1answer
27 views

Non-Negligible function arithmetics

Following the other question: If a function is known to be non-neligible by this definition, (for example $q(x)=1/x$, is it true (provable) that $poly(x)*q(x)$ (for ...
0
votes
1answer
39 views

Negligible function arithmetics

By definition of negligible function, if $q(n)$ is a negligible function, does $poly(n)*q(n)$ is also a negligible function? How can I prove it?
2
votes
1answer
35 views

Solve for a variable in mod

I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$? I tried to solve for $r$ by trying to compute ...
6
votes
1answer
86 views

What are the implications of Prime Number Theorem in Cryptography?

I know that primes and prime factorization are the basis concepts in cryptography. However, I would like to know how does the Prime Number Theorem come into picture in cryptography, since it states ...
0
votes
0answers
48 views

how to encrypt “STACK” using RSA with keys $e=133,n=2160$

$n=2257=37\times 61,\phi(n)=2160$ A B C D E F G H I J K $\space $L$\space $ M$\space $ N$\space $ O$\space $ P$\space $ Q$\space $ R $\space $S$\space $ T $\space $U $\space $V$\space $ ...
1
vote
1answer
64 views

El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
0
votes
1answer
60 views

RSA Encryption - why does it guarantee a unique cipher?

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext. How do we know all message $M$ (for ...
0
votes
0answers
62 views

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/k} \equiv 1$ (mod n)

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/x} \equiv 1$ (mod n) such that $a^{n-1} \equiv 1$ (mod $n$) and x is prime such as $x |(n-1)$. I am solving the bigger proof ...
3
votes
1answer
79 views

Probability of an ECM factor

Suppose I have a composite number $N$ divisible by some prime $p\le x.$ What is the probability that one iteration of ECM finds $p$, given parameters B1 and B2? Usually people look for factors in ...
2
votes
0answers
92 views

Homomorphic Compression

Can there be an algorithm such that: given a plaintextdata P, Q and compression function e: $$e(P + Q) = e(P) + e(Q)$$ $$e(P*Q) = e(P)*e(Q)$$ The idea is closely related to homomorphic encryption ...
0
votes
2answers
81 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
1
vote
1answer
52 views

computing the discrete log of $23^x \equiv 102 \pmod {431}$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong? "Alice and Bob agree to use a Diffie-Hellman key exchange with values p = 431 and primitive ...
0
votes
3answers
170 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.
3
votes
0answers
75 views

crack the key or not: generated key

Let $T \in F^{n \times n}$ , $F$ be a field Let $U_1, U_2 \in F^{n \times n}$ be randomly chosen by user 1 resp. user 2. user1 sends $U_1\cdot T$ to user2 , user2 sends $T\cdot U_2$ to user1 . ...
0
votes
0answers
45 views

$c$ primitive root, $a \in \{1,\ldots,p-1\}, w/ j \in \mathbb Z^+, a \equiv c^j \pmod p), a^{\frac{p-1}{2}} \equiv 1 \pmod p\implies j\text{ even}$.

Suppose c is a primitive root modulo $p$. Suppose you have a particular integer $a \in \{1,2,\ldots,p-1\}$ and you have found $j \in \mathbb Z^+$ such that $a \equiv c^j\pmod p$. Show that if ...
1
vote
0answers
92 views

Mathematical foundation crisis and the RSA

I am currently in my last year of high school and I am writing a report on cryptography from a idea historical and mathematical perspective. I am including a few of the subjects: Cantor's diagonal ...
1
vote
1answer
37 views

One-way functions and pseudorandom number generator

Is it true that if there is Cryptographically secure pseudorandom number generator then there is One-way function?
2
votes
0answers
49 views

Queston concerning cracking an RSA message

I don't have a clue how to solve this exercise: Let m be an RSA modulus, g an encryption Exponent and N be a space of Messages. You know that $k^g$ is such that $k \in S \subset N$ with an S of ...
1
vote
1answer
34 views

Good encryption exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are ...
0
votes
2answers
261 views

What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
1
vote
2answers
155 views

find the degree of a minimal polynomial for a galois field element in an efficient way (by hand)

I stumbled upon the following question in the problem section of a book on coding theory. A galois field $GF(2^4)$ is constructed as $K[x]$ modulo $1 + x^3 + x^4$ and $\beta$ is the class of $x$, so ...
2
votes
3answers
62 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
0
votes
0answers
48 views

Must the “n” in mod(n) always be prime?

I'm experimenting with mod(n) and have the following questions even after reading the Wiki page and numerous articles about the subject. Must mod(n) always be prime for cryptographic purposes? Is ...
1
vote
2answers
45 views

Proving that if $ed ≡ 1 \pmod{\frac12 φ(n)} $, then $y^{ed} ≡ y \pmod{ n}.$

This is actually the third step of the problem. It's preceded by these questions that I'm sure are supposed to lead me to solution. $n = pq$, p and q distinct odd primes First I'm supposed to show ...
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
3answers
228 views

RSA encryption without a calculator

I'm doing an RSA encryption and to get part of the solution I need to solve $$C=18^{17} \pmod{55}$$ How would I solve this problem without a calculator Thanks in advance
1
vote
2answers
81 views

How to decrypt the message?

I have difficulties with decrypting a message and i would be very glad if someone could help me to solve the following problem: Given is $n=10010$ and an encryption map ...
1
vote
1answer
189 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 ...
2
votes
1answer
172 views

cryptology beginner book

I am taking a number theory course this semester which includes a brief intro to the field of cryptology including only : Applications to Cryptology, Character Ciphers,Block and stream ...
0
votes
0answers
20 views

Why do the authors claim f(u) does not reveal anything about the random subspace X?

On pg. 8 under section 2.1 (Random Subspaces are Leakage Resilient) the authors claim "In the latter pair, the leakage function reveals nothing about the subspace X, and therefore we conclude ...
0
votes
1answer
32 views

why there is a need of one prime number while using affine cipher

I am creating an encryption application. when I use values of a & b as 2 & 3 respectively. My message get encrypted successfully, but while decrypting it does not work. Is there any formula ...
3
votes
4answers
250 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
2
votes
0answers
286 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
1
vote
1answer
124 views

Probability and crytography problem of card game

Alice and Bob are playing the following game. There are two identical decks of cards. Each of them has one of them, and both decks are shuffled randomly. Alice and Bob then reveal one card at a time ...
0
votes
1answer
65 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 ...
0
votes
1answer
34 views

2nd Order Homomorphic Encryption?

For a while the concept of Homomorphic encryption has existed which is the concept of encrypting data and still being able to manipulate it as if it was unencrypted. Would it be theoretically ...
0
votes
0answers
19 views

Search Space Function:

given a set of integers: ${x_1, x_2, ... x_n}$ Is is possible to construct a generic function $f$ such that there exists $u_1 .... u_n \in R$ where $f(u_k) = x_k$ and: $$f(x+y) = f(x) + f(y)$$ ...
6
votes
4answers
140 views

Approximation of $26!$

Peltzl's Cryptology states on page 8 that $26!$ is approximately $2^{88}$. I have tried different variations of Stirling's formula to confirm this but no luck. I know the argument is hiding in there ...
0
votes
1answer
82 views

Help me this proof! Related to RSA public key cryptosystem

Basically it is similar to the RSA algorithm. Let p and q be distince primes and let e and d be the integers satisfying $de≡1$ (mod (p-1)(q-1)). Suppose further that c is an integer with ...
0
votes
1answer
46 views

Why, in the Rabin cryptosystem, during decryption, do we get four possibilities instead of two?

The encryption algorithm : c=m^2 modn, should mean that we have two(or one) possibilities for m. Why do we get four squareroots?
1
vote
0answers
84 views

Understanding Quadratic Sieve Algorithm

I am studying Cryptography and came upon the quadratic sieve algorithm. However, I am having hard time understanding how the algorithm works. I kind of understood how the steps are followed through ...