Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
0
votes
1answer
34 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
67 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
124 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
116 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
49 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
29 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
29 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
71 views
1
vote
0answers
12 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
31 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
76 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
29 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 ...
0
votes
1answer
20 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
83 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
27 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
40 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 ...
-1
votes
0answers
15 views
How to find RSA public key from certificate? [closed]
I want to find the RSA public key used for a website. I know how to get to the certificate and only see pairs of numbers and letters and not an integer (RSA number). How do I find the RSA public key?
0
votes
1answer
22 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
50 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
51 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
23 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
61 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
58 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
170 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
13 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
70 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
68 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
33 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
votes
0answers
78 views
Prove that RSA is susceptible to a chosen ciphertext attack [closed]
Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed.
So I use the fact that the ...
1
vote
2answers
52 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
44 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
44 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
28 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
38 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
46 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
33 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 ...
0
votes
0answers
18 views
ECKS-PS algorithm: searching in encrypted data; bilinear maps
I have found an encryption algorithm named ECKS-PS (published in a paper named 'efficient conjunctive keyword search on encrypted data storage system', written by Jin Wook Byun, Dong Hoon Lee, and ...
0
votes
1answer
42 views
Compute the output of 97 after a byte substitution in AES?
I understand the framework of the calculation, however I am struggling to determine the inverse of 97 in GF(256). Any straight forward explanation would be greatly appreciated. My resources have not ...
0
votes
0answers
35 views
How do I find $m^q\pmod p$ if I already have the following values
I have $g^k\pmod p$, $m\cdot h^k\pmod p$. I also know that $g$ is ìn the set $\{1, 2, \cdots, p-1\}$ and $g$ is of order $q$, so I believe that means that $g^q = 1\pmod p \Rightarrow 1 = g^q\pmod p$. ...
1
vote
1answer
47 views
Cryptography and how it is used [closed]
I really need some help on this topic.
I am currently in third year university. I have taken this course and it wants me to write a essay in Mathematics.
I was given the topic cryptography in my ...
1
vote
0answers
39 views
Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem
If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows ...
0
votes
0answers
45 views
Can someone explain this equation?
Okay, here is the exact phrasing:
We want to get two values $A$ and $B$, where we test many values of $A$ to get the smallest value of $B$.
$B$ is the coefficient of $x^{15}$ in the result of: $(1 + ...
3
votes
1answer
77 views
Walsh spectrum of a function defined over Galois rings
Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to ...
2
votes
0answers
48 views
Are the sets $\left\{\sum_{x \in \operatorname{GR}(p^2,m)}w^{Tr(ax)} \right\}$ and $\left\{\sum_{x \in Z^m_{p^2}}w^{b \cdot x} \right\}$ equal?
Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to ...
1
vote
1answer
122 views
maximal algebraic degree of a balanced Boolean functions
While I was studying some cryptography maths, about balanced boolean functions i felt in a proposition that says
...
2
votes
1answer
48 views
Definition of Bent functions over Galois rings using Fourier transform (walsh transform)
First, note that the following definition is true:
Definition (Carlet): Let $R=GR(p^k,m)$. A function $f$ from $R^n$ to $R$ is bent if
$$|\sum_{x \in R^n} w^{Tr(f(x)-ax)}|=|R|^{n/2}$$
where $a \in ...
