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

learn more… | top users | synonyms

0
votes
0answers
8 views

Find $D$ in RSA cryptosystem

For the following encryption key $(n, E)$ in the RSA cryptosystem, compute $D$. $(n, E)= (451, 231)$ So I know $n=11*41$, so $m=400$. Now $D=$ inverse of $231 \ (mod \ 400)$. However I am not sure ...
0
votes
0answers
23 views

Cardinality of the set $\mathbb{Z}_{26}^5$

I am trying to compute the unicity for a Vigenère cipher with $m=5$ to compute this I need the sizes(cardinality) of the plaintext space and key space they are the sets $\mathbb{Z}_{26}^5$. Integers ...
1
vote
1answer
26 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 ...
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
26 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 ...
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 ...
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
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 ...
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 ...
-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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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: ...
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
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 ...
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 ...
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) ...
0
votes
1answer
99 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.
1
vote
1answer
60 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
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
0answers
23 views

Permutation certification. A cryptographic hash function for permutations?

Alice has a secret permutation $\alpha$ (a random permutation of an $n$-set; $n=18$ would be a decent choice for the application I have in mind). She wants to convince Bob that she has $\alpha$, but ...
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 ...
1
vote
1answer
24 views

Cryptology - Compare the amount of work the cryptanalyst is likely to require - Single vs. Double rotation

"Suppose a cryptanalyst suspects that SECEC SYHRI IRFET SSETE INLST AFNIA FSOAI HFSRT TEATE was obtained by a succession of two rotations with different block lengths and rotation amounts. Compare ...
1
vote
0answers
24 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 ...
4
votes
1answer
86 views

Permutations: If I know $\alpha$ and the cycle structure of $\alpha\beta$, can I find $\gamma$ for which $\gamma\beta$ also has this cycle structure?

Suppose we have two permutations $\alpha$ and $\beta$ (of a set $S$ of size $|S|=n$), and I know $\alpha$ and the cycle structure of $\alpha\beta$. But I don't know $\beta$. Can I find a ...
1
vote
1answer
36 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
0
votes
0answers
16 views

What is an embedding degree of elliptic curve?

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am ...