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

learn more… | top users | synonyms (2)

4
votes
1answer
91 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 ...
3
votes
1answer
68 views

Notation: “belongs to” with an R subscript

I've run into an expression: $x_i \in_R \mathbb{Z}_q$ – and I wonder what this means. An example paper is here, here's example in Wikipedia. Can anybody help me? Thanks in advance.
2
votes
1answer
44 views

Is there a cipher that yields two separate but valid results depending on the key?

Suppose the following. Someone wishes to encrypt a message so it is not intercepted. With traditional ciphers, if the key is guessed correctly, the message is revealed. This cipher is similar– ...
2
votes
1answer
36 views

Solve for a variable in mod

I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$? I tried to solve for $r$ by trying to compute ...
1
vote
0answers
83 views

Mathematical Basis of OAuth Encryption

There are numerous explanations of the common public-private key system available online, explaining how large primes are used to encrypt messages. Is there any similar guide to the mathematics of ...
1
vote
0answers
335 views

Diffie-Hellman key exchange public key calculation

I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
1
vote
0answers
134 views

How to proof this equation without calculating the values it self

I have the following equation. $$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$ This is part of the AKS algorithm. The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...
1
vote
0answers
51 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
1
vote
0answers
430 views

Cryptography puzzle

I'm currently broadening my knowledge in cryptography (or, at least, am trying to) and so I stumbled upon a puzzle I can't crack. It goes like this: You're given a set of pairs. The second number is ...
1
vote
0answers
86 views

A variant of the “closest vector problem” (CVP) in lattice-based cryptography

Consider a public-key scheme on lattices, such as GGH. The private key is a basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$ of a lattice $\mathcal{L}$ with good properties (such as short nearly ...
1
vote
0answers
68 views

Finding the random $r$ in a Paillier encrypted message with knowledge of the private key.

In the Paillier cryptosystem, suppose that I know a Ciphertext encrypted with some unknown random $r$ i.e. $$C = (g^m r^n) \bmod n^2 $$ I know $g, n$, the prime factorization of $n$, i.e., $pq$. I ...
0
votes
0answers
30 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
0
votes
0answers
26 views

Elliptic curve cryptography order

How do I compute an order a a point P on an elliptic curve? My question is specifically in reference to the attached photo. I understand how to do part a but I am totally lost in part b. I don't know ...
0
votes
0answers
25 views

Algorithm for solving 2PLE

I have a trouble with this article which trats an attack on the Isonorphism Problem with 2 linear secrets. At the end of page 11 the author analizes the properties of a system using a certain ...
0
votes
0answers
15 views

RSA and El Gamal

I was wondering if anyone knew where I could find some examples of encryption with El Gamal and RSA using very large primes? I wrote a code for El Gamal and RSA but I want to test it with some known ...
0
votes
0answers
13 views

calculating jacobi symbol (123456/111111111)?

I want to know how can I calculate jacobi symbol (123456/111111111) without using integer factorization? Thank you for your time in advance
0
votes
0answers
12 views

Perfect secrecy not depending on probability distribution of message space

Say we have: $D$ - probability distribution on the messages space $M$. $M_1$ - a random variable of the messages under $D$. $C_1$ - a random variable of the encryption under $D$ (and some ...
0
votes
0answers
26 views

Cracking RSA with the Same Public Key and Similar Plaintexts

I have two ciphertexts $A, B$ that were generated by the same public key $(N, 3)$ and where $m$ is the secret. We know that the plaintext of $A$ is $(37(m + 37))$ and the plaintext of $B$ is $(52(m + ...
0
votes
0answers
65 views

Rsa encryption/decryption (Updated)

1. Show that Bob can efficiently compute the encryption C(m) of the message m that he wants to send to Alice, knowing the public key but not the private key. Note: here (as well as in the rest of ...
0
votes
0answers
13 views

Computing the redundancy of language for a Vigenère cipher with m=5

Redundancy of L = 1- Entropy of L/ log base 2 {P} The Redundancy of L is given by 1 minus the Entropy of L divided by log base 2 of the Cardinality of the Plaintext space. Could someone advise me how ...
0
votes
0answers
27 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 ...
0
votes
0answers
12 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
0answers
18 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
0answers
12 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) ...
0
votes
0answers
17 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
0answers
32 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, ...
0
votes
0answers
24 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 ...
0
votes
0answers
17 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 ...
0
votes
0answers
26 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 ...
0
votes
0answers
84 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
0answers
22 views

How is the table generated for Galois Field?

If I want to generate tables for $01AB\quad 01AB$ for both addition and multiplication, how will it be generated? I am basically confused from this wikipedia example! I hope someone can clear it up ...
0
votes
0answers
48 views

How to do Rijndael MixColumns step

I am trying to go through all of the the steps in the Rijndael Encryption Algorithm using pencil and paper. I have been using ...
0
votes
0answers
105 views

Probability theory in (classical) cryptography

In (classical) cryptography we have the formal definition of a cryptosystem that is a quintuple $(M,C,K,e,d)$ where $M$ is the (finite) set of plaintexts, $C$ is the (finite) set of ciphertexts, $K$ ...
0
votes
0answers
16 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
0
votes
0answers
58 views

RSA Decryption - finding Private Key

Let p and q be primes and $e \in \mathbb{Z}^+$, with $\gcd (e, (p-1)(q-1)) = 1$. Let d be the inverse of $e \mod (p-1)(q-1)$. The decrption process where M is plaintext and C is ciphetext ...
0
votes
0answers
38 views

DLP in a Cyclic group

Let q be a prime. G is a cyclic group of order $q^2$. Show that for solving the DLP in G it's enough to solve two distinct DLPs in two groups of order q . --- We are looking for an x such that ...
0
votes
0answers
29 views

Infinite One-Time Pad

As you know, when used correctly, a one-time pad allows one to send a message, such that the only thing that can be found out about it is the maximum size (which is also the key length.) It is ...
0
votes
0answers
25 views

Provide sample matrices that could be keys in the Hill cypher

Well, to encrypt some message I need to multiply parts of it by some matrix key, and to decypher it I need to multiply the output by the inverse matrix. But I've found an excercise to provide some ...
0
votes
0answers
38 views

enumerating in pseudo random order - version 2

edit 2: what kind of statistical test do I need to get an idea of the randomness of the order of a list? The list contains all base-4 numbers from 0000 to 3333 exactly once. edit 1: I've added ...
0
votes
0answers
60 views

Using knapsack problem for digital signatures

Is it possible to use the knapsack problem for digital signatures? What I am imagining is something like the Merkle–Hellman knapsack cryptosystem, but used for digital signing, rather than encryption. ...
0
votes
0answers
52 views

how to encrypt “STACK” using RSA with keys $e=133,n=2160$

$n=2257=37\times 61,\phi(n)=2160$ A B C D E F G H I J K $\space $L$\space $ M$\space $ N$\space $ O$\space $ P$\space $ Q$\space $ R $\space $S$\space $ T $\space $U $\space $V$\space $ ...
0
votes
0answers
46 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 ...
0
votes
0answers
25 views

how does this informal proof show a particular PKE scheme is secure against non-adaptive memory attacks?

On pg. 5 of this paper the author does a section on the "Idea of the proof" using a technique known as dimension reduction. The actual proof is on pg. 13 Section 3.1 of the same paper. However, I am ...
0
votes
0answers
61 views

Addition a point on an elliptic curve with an integer value

Suppose $Q$ is a point in an elliptic curve such that $Q=dP$ and $d$ is an integer value, and $P$ is base point of that elliptic curve. Note $Q = dP$ means that $P+\cdots+P$ for $d$ times** and since ...
0
votes
0answers
82 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
0
votes
0answers
83 views

How would I create a birthday attack? (Hash Functions)

I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
0
votes
0answers
46 views

Can someone explain this equation?

Okay, here is the exact phrasing: We want to get two values $A$ and $B$, where we test many values of $A$ to get the smallest value of $B$. $B$ is the coefficient of $x^{15}$ in the result of: $(1 + ...
0
votes
0answers
79 views

Markov Chain and cryptanalysis

Where I will be able to found papers to read the state-art of the use that Markov chain in cryptanalysis. I founded this Canteaut, A. and Chabaud, F. (1998). A new algorithm for finding ...
0
votes
0answers
188 views

Cryptoanalysis of RSA

I am having trouble with this problem: Suppose that you would like to use the RSA system to send the secret message $P$ to a colleague across an insecure line of communication. Assume that you ...
0
votes
0answers
78 views

entropy of perfect cryptosystems

I am working on the product of two perfect crypto-systems and I need to prove that the product is secure. $$a -- [\text{system}\ 1] -- b -- [\text{system}\ 2] -- c$$ How can I prove that $H(a) = ...