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

learn more… | top users | synonyms (2)

7
votes
0answers
216 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) ...
6
votes
0answers
52 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
442 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
3
votes
0answers
30 views

Shamir's secret sharing interpolation problem

I try to understand this protocol - Shamir's secret sharing - threshold scheme. I got my data and I made interpolation basing on examples published on Wikipedia. You can see them below (sorry, I am ...
3
votes
0answers
78 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
72 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
247 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 ...
3
votes
0answers
82 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
99 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
68 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
62 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? ...
2
votes
0answers
35 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
2
votes
0answers
35 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
247 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
61 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
384 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
151 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
61 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
81 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
73 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
86 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
37 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
13 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
28 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
24 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
138 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
103 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
47 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
38 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 ...
1
vote
0answers
112 views

Suggest solutions book

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

Trouble Understanding Pinocchio (Verifiable Computing) Sparse Polynomials

I hope I'm asking the question properly. I've never asked anything on this exchange before, but I didn't know where else to ask. The paper in question I've almost got all the pieces to understand can ...
1
vote
0answers
33 views

Drawing a 5-stage binary LFSR with feedback Sm+5= Sm + Sm+1

Any guidance on how to draw this would be greatly appreciated I know this is more of a visual thing but I also want to go on to determine all the possible (different) cycles that are generated by this ...
1
vote
0answers
70 views

Finding a point on an elliptic curve

I have an elliptic curve with the equation $ y^2 = x^3 + ax + b $ in modulo p, where p is prime. I also have a point G on that curve. How can I find another point that isn't a multiple of G? I ...
1
vote
0answers
41 views

The number of Balanced Boolean functions

Suppose we have n-variable Boolean function (BF) and we know that the weight of a Balanced BF is $2^{n-1}$. The total number of BFs are $2^{2^n}$, Affine BFs are $2^{n+1}$ and Linear BFs are $2^n$. In ...
1
vote
0answers
42 views

Find f(x,y) = 1 if(x=y) else 0 (f must only do addition/substraction multiplication or division)

This maybe more of a computer science problem but maybe the solution lies in number theory. Given integers x,y, find F(x,y) = 1 if x=y else F(x,y) = 0 The obvious solution Negate( x-y ) cannot be ...
1
vote
0answers
29 views

What is the algebraic normal form of $F(x,y,z)= Trace (\alpha x^{24}) + x^{312} + yz$?

Let $w$ be a primitive element of $\mathbb F_{5^4}$. Let $\alpha=w^{13}$. Define, $F:\mathbb F_{5^4}\times \mathbb F_{5}\times \mathbb F_{5} \Rightarrow \mathbb F_{5} $ as, $$F(x,y,z)= Tr (\alpha ...
1
vote
0answers
153 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
1
vote
0answers
36 views

statistical analysis of discrete (non-uniform) p-values: cryptographical random data test

i'm doing a statistical analysis of a well-known cryptographic algorithm and have hit an anomaly. i need to prove that what i have found is statistically significant. i am taking block sizes of 256 ...
1
vote
0answers
27 views

Single-Digit Errors

I've been assigned the following homework problem: Given an eight digit number $a_1a_2...a_8$ and a check digit $a_9$, $7a_1+3a_2+9a_3+7a_4+3a_5+9a_6+7a_7+3a_8+9a_9 \equiv 0 \mod{10}$ ...
1
vote
0answers
58 views

determining the next random number pseudorandom number generator?

I have given 3 numbers let's say basic example x_0=5, x_1=6 and x_2=2 and modulus p is 7, ...
1
vote
0answers
88 views

Rank of Quadratic Form

Let $n,m, s \in \mathbb{Z}$ be integers satisying $n=s^2$ and $m=2n$. Let $\newcommand{\bigmatrix}[1]{ \begin{pmatrix} #1_1 & #1_2 & \cdots & #1_s \\ #1_{s+1} & #1_{s+2} & \cdots ...
1
vote
0answers
54 views

Closest vector problem

Given is a vector $v=\begin{pmatrix}2,&-1,&0,&1\end{pmatrix}$ as the shortest vector of the lattice $\Lambda (B)$, where $B$ is determined as $B=\begin{pmatrix}4 &-3 & 2 & 0\\ ...
1
vote
0answers
100 views

Given odd number $n$ count the bases to which $n$ is Euler pseudoprime

As the title says we are given an odd number $n$ and wish to find the number of bases $b$ such that $n$ is an Euler pseudoprime; That is, $\gcd(b,n)=1$ and $b^{(n-1)/2} \equiv \left( \frac{b}{n} ...
1
vote
0answers
51 views

$c$ primitive root, $a \in \{1,\ldots,p-1\}, w/ j \in \mathbb Z^+, a \equiv c^j \pmod p), a^{\frac{p-1}{2}} \equiv 1 \pmod p\implies j\text{ even}$.

Suppose c is a primitive root modulo $p$. Suppose you have a particular integer $a \in \{1,2,\ldots,p-1\}$ and you have found $j \in \mathbb Z^+$ such that $a \equiv c^j\pmod p$. Show that if ...
1
vote
0answers
127 views

Mathematical foundation crisis and the RSA

I am currently in my last year of high school and I am writing a report on cryptography from a idea historical and mathematical perspective. I am including a few of the subjects: Cantor's diagonal ...
1
vote
0answers
104 views

Understanding Quadratic Sieve Algorithm

I am studying Cryptography and came upon the quadratic sieve algorithm. However, I am having hard time understanding how the algorithm works. I kind of understood how the steps are followed through ...
1
vote
0answers
52 views

If P = NP can asymmetric key exchanges still exist?

One functions are easy to compute (ie polynomial time checking) but hard to reverse. if P = NP does that mean that asymmetric key exchanges will be reduced from polynomial computation time and ...
1
vote
0answers
80 views

Decrypting a message without the Private Key

I am given 5 different encryption modulus, N, each ranging from 78 to 88 numbers long. Then for the encryption exponent, each has the same which is 5. Then I am given 5 different encrypted messages, ...
1
vote
0answers
68 views

Asymmetric block ciphers?

Any block cipher transforms a block of $N$ bits into another block of $N$ bits based on a $\mathcal{K}$ bit key. This can be considered to be a substitution cipher on an alphabet consisting of $2^N$ ...