Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers. Consider posting your question at Cryptography.SE.

learn more… | top users | synonyms (2)

7
votes
0answers
112 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
7
votes
0answers
289 views

Homomorphic Compression

Can there be an algorithm such that, given plaintext data P,Q, and compression function e, Such that if we treat P and Q as a number (a series of bits): $$\begin{eqnarray*}e(P + Q)& =& e(P) ...
5
votes
0answers
53 views

A special case of zero-knowledge computation

This question is inspired by the disappearance of Malaysian Air 370. Let's suppose the plane crashed into the ocean. These are hotly contested waters where various countries (US, China, India, others) ...
4
votes
0answers
152 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 ...
3
votes
0answers
51 views

Why are supersingular elliptic curves useful for cryptography?

I don't know very much about cryptography and would like to learn more. I know the basics of RSA alogrithm and how elliptic curves over finite fields can be used to do something similar. But I would ...
3
votes
0answers
72 views

What minimum subset of fields of mathematics is needed to understand homomorphic encryption?

Without the luxury of full undergraduate training in mathematics, if one worked part time could the community list the smallest set of mathematical fields needed to understand homomorphic encryption? ...
3
votes
0answers
83 views

Evaluate a rational function at infinity

In the context of the Tate pairing, I would like to know that it means to `evaluate' an $\mathbb{F}_{q^k}$-rational function at $\infty$. For instance, the reduced Tate pairing is $e_n:G_1\times ...
3
votes
0answers
73 views

RSA-keys are not good?

PK := (n, e) = (1765937, 23755) SK := (n, d) = (1765937, 1734043) Can someone tell me, given these keys, what is not good about them, meaning it should not be very difficult to break it? (Except ...
3
votes
0answers
83 views

crack the key or not: generated key

Let $T \in F^{n \times n}$ , $F$ be a field Let $U_1, U_2 \in F^{n \times n}$ be randomly chosen by user 1 resp. user 2. user1 sends $U_1\cdot T$ to user2 , user2 sends $T\cdot U_2$ to user1 . ...
3
votes
0answers
74 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 ...
2
votes
0answers
25 views

Factor the RSA modulus $n = 3844384501$ knowing that $3117761185^2 \equiv 1 \pmod{n}$

As per the title, the task is to Factor the RSA modulus $n = 3844384501$ knowing that $$3117761185^2 \equiv 1 \pmod{n}\text{.}$$ $n$ being an "RSA modulus" means that it is a product of two ...
2
votes
0answers
29 views

If $g \in \mathbb{Z}/p\mathbb{Z}$ has prime order $q$, how well-distributed are the powers of $g$ modulo $q$?

More precisely: the powers of $g$, when identified with coset representatives from $\{1,\cdots,p-1\}$, consists of $q$ distinct integers. If these integers are all reduced modulo $q$ to the set ...
2
votes
0answers
46 views

The odyssey of spies: Kryptos

The part four $K4$ of Sanborn sculpture, a sculpture located on the grounds of the CIA in Langley remains unsolved. As you can read in [1], Sanborn released a clue for the 64th-69th letters in part ...
2
votes
0answers
63 views

Cryptosystem ElGamal

If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal ...
2
votes
0answers
57 views

What is a good book on Cryptography with an emphasis on algebraic aspects?

I have heard of the subject "Cryptography" but never looked much into it. But this summer, I thought is the best time to look into the subject and see if it will interest me. In U.G, I did ...
2
votes
0answers
37 views

Computing the order of a divisor in the Jacobian of a hyperelliptic curve.

Given a hyperelliptic curve of genus $g$, of equation $H: y^{2}+h(x)y=f(x)$ and defined over the finite field $\mathbb{K}$, how does one compute the order of a (reduced) divisor defined over ...
2
votes
0answers
59 views

question based RSA Algorithm

The RSA system was used to encrypt the message M into the cipher-text C = 6. The public key is given by n = p q = 187 and e = 107. In the following, we will try to crack the system and to determine ...
2
votes
0answers
282 views

Suggest solutions book

Does somebody know solutions manual for book "An Introduction to Mathematical Cryptography" by Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman?
2
votes
0answers
37 views

How many commutative block ciphers are there?

Let $K$ and $M$ and be two finite sets. Let $(G,\circ)$ be the group of permutations over $M$ under composition. Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application ...
2
votes
0answers
396 views

Bachelor Thesis - Galois Theory Research Topics?

I'm on the last semester of my bachelor's degree (undergrad degree) and I will be writing my thesis next semester. I have talked to a professor at my university and one of the topics he suggested was ...
2
votes
0answers
326 views

Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
2
votes
0answers
69 views

Queston concerning cracking an RSA message

I don't have a clue how to solve this exercise: Let m be an RSA modulus, g an encryption Exponent and N be a space of Messages. You know that $k^g$ is such that $k \in S \subset N$ with an S of ...
2
votes
0answers
591 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
173 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
63 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
79 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
93 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 ...
2
votes
0answers
103 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
20 views

Find GCD of polynomials over GF(101)

Hello all I'm teaching myself cryptography, and I'm struggling with polynomial arithmetic over finite fields. I've some what been able to teach myself how to do the arithmetic over $GF(2)$, but when ...
1
vote
0answers
38 views

Involutory key for the substitution cipher

I need to find all the involutory keys for the substitution cipher over $\mathbb{Z}_7$. I wasn't sure what can be the key for the substitution cipher. For example, for the affine cipher, $e(x) = kx + ...
1
vote
0answers
25 views

Why is this prime a bad choice for the ElGamal cryptosystem?

Using the ElGamal cryptosystem in $\mathbb{Z}_{p}^{\times}$, the proposed prime is $p = 2^{1947}\cdot 5 + 1$. The exercise asks me to show why this is a poor choice, and I can't quite do it. In my ...
1
vote
0answers
35 views

RSA public encryption: Finding p and q given $\phi(pq)$

I have a quick question: My book asks me to show that if someone were to find that value of $\phi(pq)$ then they would be able to find out p and q. Is this possible? I've seen many examples of ...
1
vote
0answers
29 views

How can I explain a Zero Knowledge Proof with minimal mathematics

I asked this earlier on how to explain a Zero Knowledge Proof to a layman. but I'm looking for a mathematical analogy that might "enhance" the superpower explanation. In that linked superpower, that ...
1
vote
0answers
18 views

How to expand Diffie-Hellman key exchange for multiple users?

To provide OTR (off the record) security for XMPP group chats we've discussed an idea for a Diffie-Hellman key exchange algorithm for multiple users. It should work as follows: Choose a cyclic group ...
1
vote
0answers
11 views

Efficiency of McEliece Cryptography

Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys. However I have never heard about the size (or length) of its ciphertext. For example, ...
1
vote
0answers
24 views

What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$. Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is ...
1
vote
0answers
22 views

Apply Pohling-Hellman to calculate the discrete logarithm

I am looking at the following example of calculating the discrete logarithm with Pohli-Hellman. The group is $\mathbb{F}_{29}^{\times}$ and we given $y=10$ and $g=3$. We want to find $0 \leq x \leq ...
1
vote
0answers
44 views

Solving for $m$ algebraically given $m^e \equiv c_1 \pmod n$ and $(\alpha m+\beta)^e \equiv c_2 \pmod n$

Given $m,n,e,c_1,c_2,\alpha,\beta \in \mathbb{N}$ and the system of congruences: $$ \begin{align} m^e \equiv c_1 &\pmod n &(1)\\ (\alpha m+\beta)^e \equiv c_2 &\pmod n &(2) \end{align} ...
1
vote
0answers
20 views

Discrete logarithm problem, existence and parity

Let $p>2$ be a prime number such that $p-1=2^st, s>0,t$ odd. Let $a,d\in \mathbb … {Z}^* /p \mathbb{Z}$ with $\left(\frac{a}{p}\right)=1$ and $\left(\frac{d}{p}\right)=-1$, where ...
1
vote
0answers
29 views

cryptographic hash functions

Suppose $ℎ: 𝑋\to 𝑌$ is a hash function. For any $𝑦\in 𝑌$ , let $ℎ^{−1}(𝑦)=\{𝑥:ℎ(𝑥)=𝑦\}$ and denote $𝑠𝑦=|ℎ^{−1}(𝑦)|$. Define $𝑁=|\{\{𝑥_1,𝑥_2\}:ℎ(𝑥_1)=ℎ(𝑥_2)\}|$. Note that N counts the ...
1
vote
0answers
16 views

Proposed two key cryptography

Q1. I do not understand why e should be public? It may be more secure to keep it private and known only to the sender and receiver. Q2. I need comments on the following proposed algorithm: Both ...
1
vote
0answers
51 views

Generator of group, Computation of discrete logarithm

The prime number $p=67$ is given. Show that $g=2$ is a generator of the group $\mathbb{Z}_p^{\star}$. Compute the discrete logarithm of $y=3$ as for the base $g$ with Shanks-algorithm. Compute the ...
1
vote
0answers
129 views

Given plaintext and ciphertext of the same length, how could one generate potential symmetric keys if encryption algorithm is unknown?

This question is about both encryption and about how and if one could transform data from one given form to another given form and back. I am given plaintext and ciphertext, both of which are the ...
1
vote
0answers
37 views

Latin Squares and Olderogge Code

So I have two Latin Squares, $A$ and $B$ that form a pair of MOLS of order $m$. I then have an Olderogge code formed from $A$ and $B$, where each binary vector of length $m^2$ is encoded as a codeword ...
1
vote
0answers
29 views

Primitive vs Irreducible

Are all irreducible polynomials primitive? If not can anyone give an example of such a polynomial that is irreducible but not primitive?
1
vote
0answers
30 views

Tidy way to represent XOR over the ring of $2^{32} - 1$

I was reading about a cipher called Speck, which defines a system of equations using Addition Mod $2^{32}$ ($\boxplus$), Bit Rotation, and XOR. If we pretend that the additions were taken over ...
1
vote
0answers
789 views

Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and ...
1
vote
0answers
266 views

Does there exist some relations between Cryptography and Algebraic Topology?

We know that there are many application of Cryptography in our real life. Are there any relation between Cryptography and Algebraic Topology? If yes, please suggest me some link or books. Thanks ...
1
vote
0answers
61 views

provably secure hash function

I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows: Gen: on input $1^n$, run to obtain ...
1
vote
0answers
43 views

Find a polynomial of degree $8$ with integer coefficients with given root

algorithm to find a polynomial $f(x)$ s.t (1) $degree(f(x))<9$ (2) Integer coefficients (3) Absolute value of coefficients $< 10^5$ (4) f(39.770525) =~ 0 about to be <<10^-10 I ...