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

learn more… | top users | synonyms

1
vote
0answers
14 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
7
votes
0answers
168 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) ...
0
votes
0answers
10 views

Shamir sharing scheme - Calculating shares

In a (2, 5) Shamir secret sharing scheme with modulus 23, two of the shares are (1,22) and (4,8). Find the secret. $$S(1) = M + s = 22 (mod 23)$$ $$S(4) = M + 4s = 8 (mod 23)$$ Eliminate through ...
0
votes
1answer
23 views

finding the inverse of a matrx

In order to decrypt a cipher text using hill cipher, we must first find the inverse matrix of a given matrix. From this link http://en.wikipedia.org/wiki/Hill_cipher, ...
1
vote
1answer
25 views

Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice. ...
1
vote
1answer
26 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
3
votes
2answers
599 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
1answer
29 views

Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is ...
1
vote
1answer
65 views

Is there an error-correcting code where almost every word could be used as a codeword?

An error-correcting code for strings of length $n$ from a $K$ letter alphabet is a partition $\Pi$ of $K^n$ together with a choice function $\pi$ on $\Pi$. Let $A_i$ for $i<M$ enumerate $\Pi$, and ...
3
votes
1answer
27 views

Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
0
votes
1answer
33 views

RSA Algorithm Question [duplicate]

Suppose the primes p and q used in the RSA algorithm are consecutive primes (meaning they differ by 2). How would you factor n = pq? The ciphertext 10787770728 was encrypted using n = 10993522499 and ...
-1
votes
2answers
322 views

Distribution of the RSA numbers

Let's take a random prime $p$. For the sake of the argument let's say $\log(p)\approx 1000$. Let's suppose all numbers between $p$ and $p+1000^2$ are composites. What is the approximate probability ...
3
votes
1answer
2k views

Find the Hill cipher key matrix that can realize this permutation

Find the Hill cipher key matrix $K$ that can realize the permutation $$f: (1,2,3,4,5) \to (3,5,1,4,2).$$ I am not sure how to find a $5\times 5$ matrix that satisfies this. My guess is ...
0
votes
1answer
22 views

Number of bits needed for Huffman code

Jake uses a Huffman code to compress i.i.d. (independent nad identically distributed) strings of symbols that come from a 5-ary alphabet ($A$, $B$, $E$, $R$, $S$) where the probabilities of occurrence ...
0
votes
0answers
16 views

Two-dimensional affine cipher

Problem: We have a two-dimensional affine cipher with $n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$, where $\mathcal{K} = \{ A,\,\,b\} $ and $b = (0,0)$. The encryption and decryption ...
0
votes
1answer
19 views

Decrypting a Vigenere cipher with affine key

Consider a cipher where the method of encryption is to perform a Vigenere cipher on a plaintext, with the key word being an affine cipher of the letters a,b,c,...,z. How strong would this cipher be? ...
0
votes
0answers
7 views

Condition on Vector Boolean Function to be Bijective

Suppose the vector boolean function be $$\begin{align} f:F^n_2 \longrightarrow F_2^n \\ (x_1,\dots ,x_n) \longrightarrow (x_2,\dots x_n,g) \\ \\ g:F^n_2 \longrightarrow F_2 \\ (x_1,\dots ,x_n) ...
1
vote
2answers
22 views

reducing exponent in modular arithmetic

Im struggling with an example excercise because I have problemes to comprehend an step in the calculation $3^{36} \mod 59 = 3^{7} \mod 59$ How can I reduce the exponent $36$ to $7$? I tried it with ...
0
votes
0answers
7 views

Relatioship b/w Bent function and Correlation Immunity

I assume that the readers know the definition of Walsh-Hadamart transform for Boolean function. An n-variable Boolean function $f$ is called bent if $W_f(\alpha)=\pm 2^{n/2}$ $\quad \forall \alpha ...
1
vote
1answer
382 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
1
vote
1answer
66 views

Does Zhang's result on primes makes RSA weaker?

I read from Finnish newspaper ( http://www.uusisuomi.fi/tiede-ja-ymparisto/72212-matemaattinen-ongelma-eli-2-300-vuotta-mies-subway-tiskin-takaa-ratkaisi#.VBwhYp09F2k.facebook ) the article of Zhang's ...
0
votes
1answer
27 views

Cryptography probability

62% of plaintext messages have even parity. 56% of odd plaintext messages have ciphertext with even parity. 48% of even plaintext messages have ciphertext with even parity. What is the probability ...
1
vote
0answers
49 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 ...
2
votes
1answer
34 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
0answers
34 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 ...
0
votes
0answers
16 views

Affine cipher and shift cipher

I have the following question: $$An\;affine\;cipher\;with\;key\;K(0,b)\;is\;equivalent\;to\;a\;shift\;cipher\;explain\;why$$ I don't think this is true, and assume it is a typo, $K(1,b)$ I would ...
0
votes
1answer
22 views

Cayley table for 2-bit integers ${Z_4}$

Let us consider the multiplication operation, denoted by $ \odot $ on the set of 2-bit integers ${Z_4}$ defined as follows: $$\eqalign{ & a \odot b = (ab\,\bmod \,5)\,\bmod \,4\,if\,a \ne 0,\,b ...
1
vote
1answer
28 views

Matrix in polynomial field

We are given a matrix $$M=\begin{pmatrix}0&1&1\\1&1&0\\1&1&1\end{pmatrix}$$ I need to show that $M$ represents multiplication by element $\beta $ in the field $F = ...
1
vote
1answer
12 views

$A^{-1}x \pmod{26}$ and coprime requirement in Hill cipher

I am reading Hill cipher from wiki page and I have been stuck on this thought for a while. Why is there a requirement for $\det(A)$ and $26$ to be coprime in Hill cipher ? Anybody familiar with Hill ...
0
votes
1answer
34 views

Notation symbol $x$ for functions

On the Modern Stream Ciphers slide #6, the following expression is used: $$ \{0,1\}^s × R ⟶ \{0,1\}^n$$ What does $×$ mean? I've seen $×$ used in a few other contexts, and I suspect it means ...
2
votes
2answers
49 views

Why does this method for the average salary problem fail?

In my Computer Science class, we were introduced to the Average Salary problem, where a group of people want to determine their average salary, but they don't want anyone to be able to determine the ...
0
votes
0answers
16 views

Cryptography: Hill Ciphers

Recently, I was given three ciphers to crack for my cryptography class. At this point, I have guessed that one of them is likely a Hill cipher (probably 3x3, as that is the most complex we have done ...
3
votes
1answer
45 views

Is it possible to find plaintext from ciphertext if (n) and (a) are known?

I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was. n = 2537 and a (or the exponent) = 11. Encrypting function: ...
0
votes
1answer
22 views

How to determine the key-matrix of a Hill cipher where the encrypted-message-matrix is not invertible?

I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals). The alphabet domain is $\{A\dots ...
0
votes
0answers
26 views

What is rational point on elliptic curve over Galois field

It is clear what is a rational point on elliptic curve, when the curve is defined over real numbers. But if it is defined over Galois field, what is a rational point? If necessary, supply an example, ...
1
vote
1answer
13 views

Exponention cipher - prove unique mapping from plain text to cipher text

At the heart of RSA, is the exponention cipher: C=M^e mod P (where C=ciphertext, M=Plaintext e=exponent and P=modulus.) How do you prove that two different plaintexts don't map to same ciphertext?
2
votes
2answers
58 views

Irreversible Math Function

Is there any function which will take two inputs, (a+b) as one input and c as another, and return a result from which c can only be computed only if a and/or b are known individually? Basically I ...
1
vote
2answers
84 views

Elliptic Curve Crypto

I had just read a primer about ECC, I see how it can be complicated. Something I haven't been able to determine is what information does the client machine get to help decrypt the data? The whole ...
2
votes
3answers
39 views

Is 6 a generator of this Group?

I've had the opportunity to learn about the mathematics behind Diffie-Hellman key exchanges, prime numbers, generators of groups, and all that good stuff. I wish I understood it, it's discomforting ...
1
vote
1answer
412 views

Affine cipher - Modular multiplicative inverse

I want to decrypt an Affine cypher. Definition: a^-1(c-b) a = 5, b = 13 Range: Alphabet (26 letters) Letter to decrypt: K (c = 10) So: = 5^-1(10-13) = 5^-1(-3) I am not sure what do to next. ...
1
vote
0answers
38 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 ...
0
votes
2answers
42 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
1
vote
2answers
122 views

RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
2
votes
2answers
47 views

Find the $4$ sq. roots of $100$ in $ U_{209}$. Identify which square root of $100$ is square.

Find the $4$ sq. roots of $100$ in $U_{209}$. Identify which square root of $100$ is square. (Not the $4^{th}$ root, but the $4$ square roots). I honestly don't even know what this question is ...
3
votes
1answer
111 views

If the same message is sent to Alice and Bob who are using different public keys, how can somoene following the channel find $m$

Alice and Bob are using different public keys, Alice is using ($N_{1,2}$) and Bob ($N_{2,2}$). A message, $m$ is sent to both of them using their RSA systems. It is also true that $N_1$ and $N_2$ are ...
1
vote
2answers
57 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
5
votes
2answers
324 views

RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
4
votes
0answers
69 views

Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
4
votes
1answer
118 views

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They ...
0
votes
1answer
97 views

How to find primitive point on an elliptic curve?

Reading about Elliptic curve cryptography, i came across primitive point's or generator point's but found nothing on how to generate such points any help would be appriciated.