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

learn more… | top users | synonyms (2)

1
vote
1answer
38 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
34 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
47 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
69 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
129 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
68 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
31 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
334 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
22 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
86 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
18 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
24 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 ...
1
vote
1answer
71 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
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 ...
0
votes
1answer
35 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
39 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
1answer
28 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 agree, since ...
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 ...
0
votes
1answer
26 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
31 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
18 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
41 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
102 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
24 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
232 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
37 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
22 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
92 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
50 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
47 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
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 ...
2
votes
2answers
55 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
130 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
70 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) ...
1
vote
1answer
253 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
63 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 ...
5
votes
1answer
152 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
29 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
59 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
50 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
28 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
101 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
48 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$, ...
1
vote
2answers
123 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 ...
5
votes
1answer
59 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
2
votes
1answer
132 views

Primitive polynomials in LFSRs

I need help proving the following theorem. I found it many books but on every single one it says that they omit the proof because it is in every good textbook. THM Let $c(x)$ be a connection ...
0
votes
0answers
29 views

Studying a code in cryptography

So,i'm given a binary code $C$ with it's generator matrix $G=(A,B)$ where $A,B$ are given matrices. The task is to study the code. First question: What does this form $(A,B)$ mean? how would $G$ look ...
1
vote
1answer
60 views

hash function not using bitwise operations

I have a need for implementing an algorithm to validate that a given message is not altered after some operations (for instance after transmission over a medium). A typical way of doing this kind of ...
2
votes
3answers
97 views

can it be proven that something is “difficult” (prime factoring for example)

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
0
votes
1answer
198 views

coding and decoding message with RSA.

First of all, I know how to solve the following exercise; the problem is that there is no solution. "In RSA, Alice chooses $p=53$, $q=63$, public key ($n=3339, e=13$). When Bob sends the message ...