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

learn more… | top users | synonyms

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$ ...
2
votes
1answer
89 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
50 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
195 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
58 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
768 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
256 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
79 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
72 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
92 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
89 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
45 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
41 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
76 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
297 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
329 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
95 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
109 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
113 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
53 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
58 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
37 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
55 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
536 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. ...
2
votes
0answers
75 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
1k 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
65 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
105 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
74 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
154 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
178 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
62 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
87 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
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?
1
vote
3answers
59 views

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod4$.

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod 4$. Would someone explain to me why exactly one of the four square roots of $x^4 \pmod {pq}$ is also a square? This result was given without proof ...
2
votes
0answers
187 views

Extending the Diffie-Hellman protocol to multiple parties

I'm going through a Coursera cryptography class, and there appeared an interesting (and currently open) problem about extension of Diffie-Hellman protocol to multiple parties, while preserving the ...
1
vote
0answers
48 views

Questions regarding the use of Index Calculus for finite fields and elliptic curves

Ok I have a few questions that hopefully some people can answer: For the Index Calculus applied to the Discrete Log Problem in $\mathbb{Z}_p^*$. I first thought that if we could find the ...
1
vote
1answer
170 views

Does “short integer solution” lattice problem admit hard instances with q=2?

Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, ...
1
vote
1answer
450 views

How to add two points on an elliptic curve

How do you add two points P and Q on an elliptic curve over a finite field $\Bbb F_{p}$. For example: adding the points $(1,4)$ and $(2,5)$ on the curve $y^2 = x^3+2x+2$ over $\Bbb F_{11}$. I know one ...
1
vote
4answers
82 views

if $a b \bmod n = x$ then is it true that $x b \bmod n = a$?

I am a student of computer science and I'm doing cryptography; I need to optimise the way I calculate modulus. What I'am doing is like this: $$14 \cdot 16 \equiv 3 \bmod 17$$ $$3 \cdot 16 \equiv 1 ...
0
votes
1answer
154 views

Calculating Probabilities for Substitution Ciphers using Frequency Analysis

I have been trying to put together a tool that can take in cipher text encrypted via a simple substitution cipher and calculate the most likely "key" (that is, how the plain text letters were mapped ...
1
vote
1answer
65 views

Maximum order for $x$ in $g^x \equiv 1 \mod {n}$, when n=pq

I am currently trying to learn about the ElGamal Digital Signature scheme. It is based on the discrete logarithm problem, where it is computationally infeasible to find $x$ in $y=g^x \mod{p} $), if ...
2
votes
1answer
187 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
2
votes
0answers
92 views

Decryption in the Merkle-Hellman cryptosystem

In a Merkle-Hellman cryptosystem, plaintext message units are of length $3$ over the alphabet $$ \begin{array}{cccc} ...