Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
2
votes
1answer
15 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
42 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
22 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 ...
2
votes
0answers
32 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
53 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
55 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
39 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
20 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
38 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
125 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
69 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
39 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
45 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
77 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 ?
0
votes
2answers
170 views
RSA: Prove that all messages encrypt to itself
RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
0
votes
1answer
147 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
50 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
30 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
32 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 ...
0
votes
1answer
74 views
1
vote
0answers
19 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, ...
0
votes
1answer
34 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
77 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
39 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
25 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
93 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
34 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}
...
2
votes
1answer
41 views
RSA cryptography question
RSA user Alice has a public key ($n_A=pq$,$e_A$), where $p$ and $q$ are different primes such that the least common multiple $l$ of $p-1$ and $q-1$ is relatively small (i.e. $l$ is close to ...
0
votes
1answer
23 views
congruence modulo and equality
why in cryptography most of the equalities written in the form of
$$a:=b$$
why not we write $a=b$
why in congruence modulo $a \equiv c \pmod b$ that bracket is put. Is it refers the priority.
can ...
0
votes
1answer
51 views
Finite field integers
can some one explain the following terms
$Z_n^N$, $F_q^N$ and $F_q^*$
and
why the bi-linear pairing is used in cryptography.
0
votes
0answers
13 views
predicate based encryption
I am not clear how the predicate based encryption is working especially the token generation.
can any one help me with an example or can you suggest some site where the example is given for the ...
0
votes
1answer
52 views
Linear matrix cryptosystem
You intercept the following message:
$VOBG!?FRWZ?RPAGYJFGWX?$
which was sent using a linear matrix cryptosystem $[x, y]^{T} \rightarrow A[x,y]^{T}$ on digraph message units (i.e. each unit consists ...
0
votes
1answer
27 views
Affine encryption and frequency analysis. Need help seeing where I'm going wrong.
QUESTION:
An affine encryption function $f(n) \equiv an+b \ mod(41)$ has been used on plaintext composed of symbols from the alphabet
$$
\begin{array}{cccc}
...
3
votes
1answer
63 views
Easy way to calculate $614^7 \pmod{2609}$?
We are starting to go over Cryptography in our Number Theory class and we are doing an example of encrypting a message using something similar to RSA method.
I have I need to find what
$$614^7 ...
-1
votes
3answers
59 views
Cryptology number theory
By using Chinese Remainder Theorem, how many solutions are there to $b^{1104} = 1 \pmod{5*13*17}$ with $gcd(b, 1105) = 1$?
11
votes
3answers
173 views
What is necessary to exchange messages between aliens? [closed]
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
0
votes
0answers
15 views
predicate based indexing
Let the set of plain texts to be $E=\Bbb Z_N^n$
The class of predicates to be $F=\{f_\vec v\mid\vec v\in\Bbb Z_N^n\}$
where $f_\vec v (\vec x)=1$
iff $\langle \vec v,\vec x \rangle =0$
where ...
1
vote
3answers
72 views
Is every pure set of permutations a group?
Let $\mathcal{P}$ be the set of permutations over a finite set $\mathcal{S}$, with $|\mathcal{P}|$=$|\mathcal{S}|!$
$(\mathcal{P},\circ)$ is a finite group, where $\circ$ is composition.
A subset ...
1
vote
2answers
73 views
How do you determine if an elliptic curve over a finite field is cyclic?
I know the group order and the points of the elliptic curve $y^2 = x^3 + Ax + B$, but I am confused on how to determine if they from a cyclic group
The curve $y^2 = x^3 + 2x +2$ in $\Bbb F_{11}$ ...
2
votes
1answer
35 views
Formula/Algorithn for Exponential factoring?
Given $s = a^b$ find $a$ and $b$. my first algorithm was the obvious brute force method of checking all $b$ roots or dividing by all possible $a$. But I am wondering if there is a more efficient ...
1
vote
2answers
58 views
Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)
I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :)
this is a link to a previous post which quickly ...
1
vote
0answers
48 views
Is discrete ultralogarithm harder than discrete logarithm?
Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing
$g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
0
votes
1answer
23 views
Explanation on step $\rho$ of the SHA-3 algorithm
I'm working on implementing SHA-3 in a PIC microcontroller.
In the block permutation, I don't quite understand step $\rho$:
Bitwise rotate each of the 25 words by a different triangular number 0, ...
0
votes
0answers
48 views
How would I create a birthday attack? (Hash Functions)
I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
0
votes
0answers
30 views
Classical McEliece Public Key
I am trying to implement the McEliece crytosystem. My question is How I will be able to choose the appropriate randomic $S$ and permutation $P$ matrix?. I ask this because when I trying obtain the ...
1
vote
1answer
43 views
Show that the decryption transformation for the El Gamal cryptosystem works.
Want to show that, if $P$ is the original plaintext block and $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then
$$(\gamma^a)'\delta \equiv P \pmod p$$
So, we have:
$\gamma = \alpha^k ...
1
vote
2answers
51 views
Discrete Logarithm
If $p$ is a prime and $a,b$ are integers not divisible by $p$ such that $a^x \equiv b \pmod p$ with $0 ≤ x < o_p(a)$, then we define $x = L_a(b)$ and say $x$ is the discrete logarithm of $b$ ...
1
vote
1answer
35 views
Describe the set of rational points on the curve
Describe the set of rational points on the curve
$x^2-7y^2=2$
Given that $(3,1$) is on the curve
8
votes
2answers
169 views
Who is the oldest? (in a non-revealing way)
How can a group of people figure out who is the oldest, without revealing any other information?
Revealing all the ages to a trusted third party is not allowed. Preferably I'm looking for solutions ...
1
vote
0answers
36 views
Adding and multiplication in jacobian coordinates
Please tell me how i can to derive formulas for adding and multiplication of 2 points in jacobian coordinates $((x,y)=(\frac{X}{Z^2},\frac{Y}{Z^3}))$ over elliptic curve? Thanks a lot beforehand.
I'm ...
