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
0answers
62 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
1
vote
0answers
41 views

Discrete Logarithm Problem in $\mathbb{F}_{p}$ and using Elliptic curves

I want to learn about the hardness of the DLP in $\mathbb{F}_{p}$ and using Elliptic curves, and the best attacks against each. I want to be able to compare the hardness of the problem in the two ...
1
vote
0answers
53 views

Questions regarding the use of Index Calculus for finite fields and elliptic curves

Ok I have a few questions that hopefully some people can answer: For the Index Calculus applied to the Discrete Log Problem in $\mathbb{Z}_p^*$. I first thought that if we could find the ...
1
vote
0answers
69 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
1
vote
0answers
44 views

Adding and multiplication in jacobian coordinates

Please tell me how i can to derive formulas for adding and multiplication of 2 points in jacobian coordinates $((x,y)=(\frac{X}{Z^2},\frac{Y}{Z^3}))$ over elliptic curve? Thanks a lot beforehand. I'm ...
1
vote
0answers
55 views

Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem

If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows ...
1
vote
0answers
87 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
367 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
135 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
52 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
97 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
71 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
8 views

What is the proper way to generate a key in Merkle-Hellman Knapshack Cryptosystem?

This article says that, if a message is 8-bit, then there should be 8 elements in the Super Increasing Sequence. ...
0
votes
0answers
6 views

how to calculate number of points on an Elliptic curve over prime field? suggest any best method

$y^2=x^3+a*x+b\pmod p$. For this elliptic curve over prime field, how to calculate number of points lies on the curve? suggest any best method.
0
votes
0answers
35 views

Solving RSA cipher without calculator

I have a question: Encrypt the message UPLOAD using RSA with $n=3\cdot 31$ and $e =17$. My question is, how can I solve this with a calculator and in an efficient manner due to being in an exam ...
0
votes
0answers
18 views

Why AES uses polynomials instead of numbers

In AES, the numbers actually represent polynomials and all operations like addition, multiplication have rules according to modular polynomial arithmetic. I don't understand the need to have ...
0
votes
0answers
22 views

Primitive vs Irreducible

Are all irreducible polynomials primitive? If not can anyone give an example of such a polynomial that is irreducible but not primitive?
0
votes
0answers
36 views

How does the factor command on the TI-89 works?

So to put my question in context, I am working on the following problem. Let $N=1291233941$. Eve's magic box tells her the following three encryption/decryption pairs for $N$: $$(1103927639, ...
0
votes
0answers
40 views

What's the expected number of hashes before you find a match?

For any request to a server, the server responds by sending the requestee a random number $r$ and another number $n$. The requestee must produce a solution $s$ such that $\operatorname{HMAC_r(s)}$ ...
0
votes
0answers
70 views

Affine cipher does not satisfy the diffusion property.

Generally, we know that substitution ciphers do not have the property of diffusion. And affine ciphers is the special case of substitution ciphers. But how can we prove that affine cipher does not ...
0
votes
0answers
34 views

Of what use is my code for finding prime numbers of a certain size?

I've developed a bit of mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
0
votes
0answers
30 views

Formulate a general version of this cryptosystem

The exercise describes a public key cryptosystem that requires Bob and Alice to exchange several messages. We illustrate the system with an example. Bob and Alice fix a publicly known prime ...
0
votes
0answers
17 views

Time estimation and big-O notation

Let a and m be elements of $\mathbb{Z}$ where m is positive. How can I show that the inverse of $a$ can be computed in $O(log^3m)$ bit operations? I thought that I should find the greatest common ...
0
votes
0answers
12 views

Diffie-Hellman decision problem

I am looking at the Diffie-Hellman protocol. The Diffie-Hellman decision problem (DDH) is the following: We are given $g, g^a, g^b, g^c$ and we want to check if $g^{ab}=g^c$. where $g$ is an ...
0
votes
0answers
22 views

Verify no elements of a list have been removed

I have an sequence of $k$ elements, $\{a_k\}$. Say at any given moment I add an element $a_{k+1}$ to the sequence. Is there any way to verify the sequence has not been altered, without checking each ...
0
votes
0answers
71 views

Find a point $P$ on an elliptic curve, given $2P$

Let $E$ be the Elliptic curve given by $Y^2=x^3+5x-6$ and suppose $P$ is a point on $E$ over $\mathbb F_{65537}$ with $2P=(7283,24272)$. Find $P$. I approached this question as follows. ...
0
votes
0answers
43 views

Elliptic Curve finding point of a curve backward?

Given $E: y^2=X^3+5X-6$ over $F=(65537)$ with $2P=(7283, 24272)$ how to find $P$ Can anyone provide an example in steps?
0
votes
0answers
30 views

Rabin cipher question

I am getting wrong answer to this question. Any one else too has solved it ? Decrypt the Ciphertext message 1819 0459 0803 that was encrypted using the Rabin Cryptosystem with b= 3 and n= 47 *59
0
votes
0answers
22 views

1-2 Oblivious Transfer and its simulation by ordinary OT

The version of 1-2 oblivious transfer mentioned in Even, Goldreich and Lempel [1985] has the provision that the receiver, Bob, can discover with probability > 1/2 if the sender, Alice, sends the same ...
0
votes
0answers
22 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
0
votes
0answers
19 views

What's the implication of the Frobenius automorphism to DLP

Given a field, e.g. GF(p^x), does the existence of a Frobenius automorphism affect the difficulty of calculating the discrete log in that field? How about other morphisms?
0
votes
0answers
31 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
35 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
26 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
49 views

RSA and El Gamal Algorithms

I have to write a short report about RSA and El Gamal algorithms in cryptography. I just need to summarize them (how one would calculate the various components, what their strengths and weaknesses ...
0
votes
0answers
28 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
13 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
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
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) ...
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
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, ...
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 ...
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 ...
0
votes
0answers
101 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
25 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
62 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
60 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
42 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
41 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
78 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. ...