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

learn more… | top users | synonyms

3
votes
1answer
155 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
59 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
62 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} + ...
0
votes
2answers
92 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
98 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
60 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
20 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
130 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
70 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
72 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
114 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
79 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
0answers
38 views

Hash functions that produce a point on an elliptic curve.

I see in some cryptographic papers, that the authers of those papers utilize of a hash function such that that hash function converts an integer value or octet-string value as input, to a point on an ...
0
votes
1answer
171 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
57 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
637 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
203 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
76 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
67 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
70 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
91 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
88 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 ...
0
votes
0answers
42 views

Show that we can use d' for the decrypting exponent, where d' is a solution of ex=1 (mod lema(m)).

Let $p, q$ be distinct odd primes and let $m' = \text{lcm}(p-1, q-1)$, the least common multiple of $p-1$ and $q-1$. Suppose we set up an RSA cryptosystem with a modulus $m = pq$ and an encrypting ...
1
vote
0answers
34 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
72 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
187 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
286 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 ...
1
vote
3answers
93 views

How would you reverse this double-variable equation?

So I have an example function: $$f(a,b) = \frac 12 ((a+b)^2 + 3a + b)$$ It "encodes" two variables into one unique number. Assuming a and b are always positive, how would you write a function to ...
2
votes
1answer
103 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
91 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 ...
1
vote
1answer
47 views

Is it possible for a singular matrix to be invariant on this interval?

I'm creating a code that that uses a matrix or matrices as a key. For example, given each string of $n$ letters, construct it into a vector using its position in the alphabet, and multiply it by an ...
0
votes
1answer
52 views

Interpolating a linear transformation

I'm experimenting with some rudimentary ideas for data encryption (I've never formally taken a cryptology class). An idea that I had for an encryption was to use matrices. So I treat a data set as ...
1
vote
0answers
35 views

Discrete Logarithm Problem in $\mathbb{F}_{p}$ and using Elliptic curves

I want to learn about the hardness of the DLP in $\mathbb{F}_{p}$ and using Elliptic curves, and the best attacks against each. I want to be able to compare the hardness of the problem in the two ...
2
votes
1answer
54 views

How to compute $x$ and $y$

How can one find in an efficient way $x,y \in \mathbb{Z}$ with max$\{|x|,|y|\} > 0$ as small as possible such that $\mid \pi x + e y \mid < 10^{-4}$ ? I have reduced the following lattice ...
2
votes
1answer
404 views

How to compute the modular multiplicative inverse on WolframAlpha?

$e = 17$ $\varphi(3233) = (61 - 1)(53 - 1) = 3120$ Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding d = 2753. ...
1
vote
0answers
72 views

has any cycle found in MD5?

We are not sure whether MD5 has fixed point or not. But since the sample space is finite, it must have cycles: $$ A →(MD5)→ B →(MD5)→ C →(MD5)→ D →(MD5)→ A $$ Has any research been done on MD5 to ...
1
vote
1answer
730 views

multiplication in GF(256) (AES algorithm)

I'm trying to understand the AES algorithm in order to implement this (on my own) in Java code. In the algorithm all byte values will be presented as the concatenation of its individual bit values (0 ...
3
votes
0answers
63 views

Does there exist an operation like bitwise-xor over non-power-of-2 domains?

I want a function for enciphering a single letter that takes two letters as input, produces one letter as output, and has the same properties as bitwise XOR. The problem is that the range of inputs ...
0
votes
0answers
81 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
3
votes
1answer
97 views

Is the number of quadratic nonresidues modulo $p^2$, greater than the number of quadratic residues modulo $p^2$?

Let $p$ be a prime. The number of quadratic nonresidues modulo $p^2$, is greater than the number of quadratic residues modulo $p^2$. Is that statement true or false? Why? Thank you.
0
votes
2answers
48 views

Determine amount of congruent numbers

I found the claim in a paper that there are at max 8 integers mod $2^{130}-5$ congruent to one integer mod $2^{128}$. $$u \pmod {2^{130}-5} \equiv g \pmod {2^{128}} \quad\text{ with }u \in U \quad ...
0
votes
0answers
50 views

Formula for checking the probability of a character appearing multiple times consecutively in an encrypted string

I am a young CS student with a specific interest in Cryptography, but I am relatively new to the field. Yesterday I came across a question I could not answer by myself, so I thought I'd ask some more ...
0
votes
0answers
73 views

How to calculate RSA Cryptography for small prime numbers?

Probably duplicate of Why are very large prime numbers important in cryptography? But my question is,what if we start with two small prime numbers say $p = 3$, $q = 5$ and $n = pq = 15$, $\phi(n) = ...
7
votes
1answer
151 views

Are there practical applications to the new prime pair proof?

I've recently heard that its been proven that the set of prime pairs that are separated by no more than 70,000,000 is infinite. Does this have any impact on cryptography or another practical ...
0
votes
3answers
148 views

Mathematics for cryptography.

Besides number theory, what other areas should I study for crypto. I did my undergrad in Comp Sci so the crypto course didnt have much mathematical topics. But for a grad specilisation in crypto I ...
1
vote
1answer
58 views

RSA encryption theory - modulo theory

I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem ...
0
votes
1answer
76 views

RSA cryptosystem: If $k$ is a multiple of $\phi(N)$, then $k=2^t r$ with $r$ odd and $t\geq1$

I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3. Fact 1: Let $(N,e)$ be an RSA public key. Given the private ...
0
votes
1answer
82 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
221 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$.