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

learn more… | top users | synonyms

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
299 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
161 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
63 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
48 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
71 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
235 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
82 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
202 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
179 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
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
319 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
327 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
125 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
73 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 ...
6
votes
4answers
141 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
87 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
47 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
86 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
46 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
69 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
44 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
185 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
63 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
71 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
137 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 ...
3
votes
2answers
111 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
63 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
160 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
81 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
94 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
147 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$ ...
2
votes
1answer
92 views

Modular exponentiation WITHOUT modular exponentiation

Given that 719 is prime, find the least positive residue of $11^{721} (mod\ 719)$, without using modular exponentiation. So, I know how to use modular exponentiation and have done it to get the ...
0
votes
1answer
227 views

Real-world example for Diffie–Hellman key exchange

I read in Wikipedia about the Diffie–Hellman key exchange. But i can't imagine numbers which are hard to guess. Can anybody give me a real-world example for $p$, $g$ and the two random secrets?
0
votes
0answers
60 views

Addition a point on an elliptic curve with an integer value

Suppose $Q$ is a point in an elliptic curve such that $Q=dP$ and $d$ is an integer value, and $P$ is base point of that elliptic curve. Note $Q = dP$ means that $P+\cdots+P$ for $d$ times** and since ...
12
votes
6answers
959 views

How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
0
votes
1answer
292 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
1
vote
1answer
86 views

Diffie-Hellman key exchange for three user.

Assume that there are three users that have their own secret key $d_i$ and corresponding public key $Q_i = d_i G$ such that $Q_i$ is a point in an elliptic curve. Now I'm looking for a solution to ...
1
vote
1answer
72 views

How to determine which encryption system is being used?

I came across this question in a local contest. I was not able to solve it at that time. Also, no solution was provided. I was wondering if someone can help me to understand how to tackle this kind ...
0
votes
1answer
74 views

Cryptography finding $\bar{k}$

In order to transmit messages in a secure way, some sort of scrambling or encoding of the message is necessary. Without doing so, sensitive information about intended troop movements or information ...
4
votes
1answer
93 views

Solving $x^y + y^x = a$

If $a$ is given how can I calculate $x^y$ and $y^x$ the fastest way? Is there any other way than brute forcing? How is this type of equation called? Let's say $x$ and $y$ must be $>1$ and non ...
2
votes
1answer
94 views

Cyber paper and pencil

Imagine that you would like to write down your passwords or other critical information into a sheet of paper. Could an algorithms without using a computer be so good as to avoid people of cracking ...
1
vote
0answers
47 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
0
votes
1answer
78 views

Cyclic Groups: Modulo operations in exponents possible?

I'm trying to follow CCat's Zero Knowledge Proof example, which was quite similar to the $\Sigma$-protocol example in my books. And whith both of them I'm struggeling. When I try to test CCats ...
3
votes
1answer
350 views

Adding points of an elliptic curve over a finite field

I'm a bit confused with how fractions are handled with adding points of elliptic curves over finite fields. Below is an example from the text which I am trying to understand: The part that ...
0
votes
1answer
388 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 ...