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

learn more… | top users | synonyms

0
votes
0answers
59 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 ...
-1
votes
1answer
67 views

Encrypt the message m = 4 [closed]

a) Let p = 11. If e = 7 , show the steps and find d. b) Encrypt the message m = 4 c) Decrypt the result of part (b). GCD(7,p-1) = 1 there is a d such that (m^e)^d = m d satisfies ed - (p -1)k = 1
3
votes
1answer
75 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 ...
1
vote
0answers
83 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
79 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
51 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
163 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
43 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
90 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
36 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
215 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
148 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
61 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
46 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
224 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
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 ...
1
vote
1answer
159 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
194 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
235 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
123 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
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 ...
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
139 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
0answers
28 views

Adversarial Secret Sharing [duplicate]

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they ...
0
votes
1answer
80 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
79 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 ...
1
vote
0answers
45 views

If P = NP can asymmetric key exchanges still exist?

One functions are easy to compute (ie polynomial time checking) but hard to reverse. if P = NP does that mean that asymmetric key exchanges will be reduced from polynomial computation time and ...
1
vote
0answers
64 views

Decrypting a message without the Private Key

I am given 5 different encryption modulus, N, each ranging from 78 to 88 numbers long. Then for the encryption exponent, each has the same which is 5. Then I am given 5 different encrypted messages, ...
1
vote
1answer
43 views

Decrypting a message?

I would like to ask for a little help about the following problem, i got stuck in it and have no idea how to proceed to get the answer which Wolfram Alpha gives (of course, i am not allowed to use the ...
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 ...
3
votes
0answers
61 views

Notation: “belongs to” with an R subscript

I've run into an expression: $x_i \in_R \mathbb{Z}_q$ – and I wonder what this means. An example paper is here, here's example in Wikipedia. Can anybody help me? Thanks in advance.
0
votes
1answer
66 views

showing a code exists given the lower bound of its dimension (with respect to its length and distance)

How do I show that there exists a code $C$ of length $n$ and distance at least $d$ such that $ max_{length(C) = n, d(C) \geq d} \mid C\mid \geq \frac{2^n}{\binom{n}{0} + \binom{n}{1} + ...
1
vote
2answers
115 views

Checking if a linear code exists - singleton , hamming and gilbert-varshamov bounds do not help.

Suppose I want to check if a (11, 6, 4) code exists. I cannot prove non-existence using the singleton and the hamming bound. I also cannot prove existence using the gilbert-varshamov bound. I'm not ...
2
votes
2answers
101 views

Why modular arithmetic in secret sharing?

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a ...
1
vote
0answers
62 views

Asymmetric block ciphers?

Any block cipher transforms a block of $N$ bits into another block of $N$ bits based on a $\mathcal{K}$ bit key. This can be considered to be a substitution cipher on an alphabet consisting of $2^N$ ...
0
votes
0answers
24 views

how does this informal proof show a particular PKE scheme is secure against non-adaptive memory attacks?

On pg. 5 of this paper the author does a section on the "Idea of the proof" using a technique known as dimension reduction. The actual proof is on pg. 13 Section 3.1 of the same paper. However, I am ...
1
vote
1answer
68 views

What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say "We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously ...
0
votes
1answer
152 views

Cryptography textbook

Might come as a rather strange request but does anyone know a textbook on cryptography that is small and short, say around 300 pages max. I am tired of having a sore shoulder from carrying 5 heavy ...
1
vote
0answers
76 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
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 ...