Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
4
votes
1answer
77 views
Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?
The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all?
With the ...
3
votes
1answer
68 views
Derivation of freshness of a message using BAN Logic
Given:
We have a principal $A$ that believes that $fresh(K_A)$ and $fresh(K_A^{-1})$, where $K_A$ and $K_A^{-1}$ are a public and private key pair generated by $A$.
$A\ believes\ B\ said\ ...
1
vote
1answer
22 views
What is a memoryless nonlinear boolean function?
I have been reading about shift register based keystream generators in cryptography. One usual method of generating keystream sequences is feeding the output of several Linear Feedback Shift Registers ...
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 ...
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 ...
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
39 views
Perfect Secrecy, Encryption
An encryption scheme $(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ over a message space $M$ is perfectly secret if and only if for every probability distribution over $M$, every message $m\in M$, and ...
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 ...
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
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 ...
2
votes
0answers
38 views
Probability of a characteristic in Blowfish
I'm trying to understand a cryptanalysis of the Blowfish cipher, and I need to calculate the probability of collision in the cipher's S-boxes. Basically an S-box is a list of 256 semi-random 32-bit ...
2
votes
0answers
47 views
(Please check working) Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$
Please check the working and final answer to the question:
Question:
Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$
My working:
$\phi(3737) = \phi(37) \times ...
2
votes
0answers
67 views
Interesting Characteristic About the RSA Cryptosystem
I know that decryption in the RSA cryptosystem works because$$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv ...
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 ...
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, ...
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$ ...
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 ...
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 ...
1
vote
0answers
34 views
Mathematical Basis of OAuth Encryption
There are numerous explanations of the common public-private key system available online, explaining how large primes are used to encrypt messages. Is there any similar guide to the mathematics of ...
1
vote
0answers
75 views
Collision resistant hash function
A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.
...
1
vote
0answers
152 views
Diffie-Hellman key exchange public key calculation
I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
1
vote
0answers
127 views
How to proof this equation without calculating the values it self
I have the following equation.
$$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$
This is part of the AKS algorithm.
The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...
1
vote
0answers
34 views
Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability
I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
1
vote
0answers
247 views
Cryptography puzzle
I'm currently broadening my knowledge in cryptography (or, at least, am trying to) and so I stumbled upon a puzzle I can't crack. It goes like this:
You're given a set of pairs. The second number is ...
1
vote
0answers
56 views
A variant of the “closest vector problem” (CVP) in lattice-based cryptography
Consider a public-key scheme on lattices, such as GGH.
The private key is a basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$ of a lattice $\mathcal{L}$ with good properties (such as short nearly ...
1
vote
0answers
49 views
Finding the random $r$ in a Paillier encrypted message with knowledge of the private key.
In the Paillier cryptosystem, suppose that I know a Ciphertext encrypted with some unknown random $r$ i.e.
$$C = (g^m r^n) \bmod n^2 $$
I know $g, n$, the prime factorization of $n$, i.e., $pq$. I ...
1
vote
0answers
99 views
Feasibility of a cryptography transformation
This is a follow-up of the question: Transformation
We are given
$$g^{1/(x+m)},$$
(it is not possible to find $\frac{1}{x+m}$ due to the Discrete log problem), can we find a $k$ such that
...
1
vote
0answers
486 views
Solving Diffie–Hellman problem for low primitive root
What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)?
Of course you could brute force it but I'm interested in ...
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
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 ...
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 ...
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
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$. ...
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 + ...
0
votes
0answers
20 views
If the plaintext is “HELPMEAR” and the block size is 5, determine the key
We first add on 2 random characters XX to the end to make the number of characters equal to 10.
So we get:
HELPMEARXX
which we can seperate into. (I think)
XXRAE MPLEH
So the key should be 2 ...
0
votes
0answers
47 views
Markov Chain and cryptanalysis
Where I will be able to found papers to read the state-art of the use
that Markov chain in cryptanalysis. I founded this
Canteaut, A. and Chabaud, F. (1998). A new algorithm for finding ...
0
votes
0answers
29 views
How can we determine if two discret logarithms are equal?
Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$, we have a list $y_{1},y_{2},...,y_{n}$ of elements in $Z^{*}_{p}$ such that for every $i\in ...
0
votes
0answers
19 views
Computing discret logarithm $log_{g}(h)$ such that $g,h$ are generators for the cyclic group $Z^{*}_{p}$
Let $p$ be a prime number, $g, h$ be generators of the cyclic group $Z^{*}_{p}$ , and $f$ be defined as:
$f : \lbrace 1, . . . , p − 1\rbrace^{2} → Z^{∗}_{p}; (x,y) \rightarrow g^{x}h^{y}\;mod\;p$.
...
0
votes
0answers
77 views
Eavesdropping but not CPA Secure
Show assuming the existence of a pseudorandom function that there is
a encryption scheme which is indistinguishable for multiple encryptions
in the presence of an eavesdropper, but is not CPA secure.
0
votes
0answers
56 views
PrimeFactorUsingSpreadsheet-Positive integer maximum of 15 digits (from 1 to 999,999,999,999,999)
I need your help or suggestion to my project "Prime Factor By Saccuan's Lab"
Prime Factor Using Spreadsheet-Positive integer maximum of 15 digits (from 1 to 999,999,999,999,999) and if you can to ...
0
votes
0answers
139 views
homomorphic encryption
Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another (possibly different) algebraic operation performed on the ...
0
votes
0answers
325 views
Hill cipher known-plaintext attack with unknown alphabet
I'm trying to understand a cryptanalysis of a variant of the Hill cipher using an unkown alphabet through a known-plaintext attack.
The classic Hill cipher use an $n\times n$ inversible matrix
$K
...
0
votes
0answers
46 views
cryptographyVs matrices
I need a good example(s) and justification to the following. If any one can help, I am so glad to them. I understand the original computation. However, I am little confused in writing coding and ...
0
votes
0answers
77 views
public key crypto
Okay, i have basic knowledge of public key crypto and factoring but:
assume i have LOTS of high value sites I want to attack, lets say banks. Each has a public key pq to crack
assume I gather all ...
0
votes
0answers
151 views
Cryptoanalysis of RSA
I am having trouble with this problem:
Suppose that you would like to use the RSA system to send the secret message $P$ to a colleague across an insecure line of communication. Assume that you ...
0
votes
0answers
103 views
Showing Elliptic Curves are irreducible
Suppose an elliptic curve defined over a field $K$ has form $y^2 + h(x)y = f(x)$ where $h(x), f(x) \in K[x]$. $h(x)$ has degree 0 or 1 and $f(x)$ has degree 3 or 4. Moreover, this equation is ...
0
votes
0answers
59 views
entropy of perfect cryptosystems
I am working on the product of two perfect crypto-systems and I need to prove that the product is secure.
$$a -- [\text{system}\ 1] -- b -- [\text{system}\ 2] -- c$$
How can I prove that $H(a) = ...
0
votes
0answers
207 views
Index Calculus for Discrete Logarithm Problem
I am trying to implement index calculus algorithm for discrete logarithm problem.
In general the algorithm works like this :
Input: Zp, order d, generator a, b element of Z
Output: log_ab
1- find a ...
