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

learn more… | top users | synonyms (2)

0
votes
0answers
29 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
1answer
11 views

solving ANF equations

Can anyone suggest a method of solving boolean equations in ANF form? Boolean equations in ANF form are equations of the form of xor of products of boolean variables. For example ((x1 and x2) xor (x2 ...
0
votes
1answer
58 views

Breaking RSA code

I will be grateful for some tips on how to bite a task like so: I need to break a RSA code. I know that public key is $n=462257, e=13$. I also have cryptogram $c=139552$. The goal is to find a number ...
4
votes
1answer
68 views

How does the Enigma machine ensure that no letter is substituted for itself?

In Alan Turing: The Enigma Andrew Hodges describes how the letter encodings performed by a German Enigma machine "would always be swappings" (original emphasis). And goes on to say that There was ...
0
votes
0answers
41 views

Is there any real world application for simplifying roots? [closed]

I am someone who graduated college at the end of last year, and am now working in IT Security. After nerding out over cryptography with my boss, talking about RSA encryption's usage of factoring ...
0
votes
2answers
27 views

Exponentiation in Modular Arithmetic

I feel like this is a fairly straightforward question, but I've been having a great deal of difficult computing one modular arithmetic expression. It's this: $9 ≡ 3^a \pmod{17}$ How does one go ...
1
vote
3answers
26 views

affine cipher $ax+b \mod m$

I have an affine chipher $ax+b \mod m$ For what values $a,b$ is this an injective encryption function? From what i understand thats the case when $a$ and $m$ are coprime, so $gcd(a,m)=1$ and the ...
1
vote
1answer
49 views

Artificial Integer?

Consider a function $$ f: \Bbb{Z} \rightarrow \Bbb{Z} $$ Over the integers. Furthermore consider a number E such that there doesn't exist an integer R such that $f(R) = E$ or formally stated $$ E ...
0
votes
0answers
39 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
65 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
2answers
46 views

Euler's Totient Function and Cryptography Question

I'm working on a problem set for a class on intro computing and cryptography. I'm being asked to find the $n = pq$, where $p,q$ are integers (not necessarily prime), such that $\phi(n)=$ ...
0
votes
0answers
33 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
19 views

Discrete Log Problem

I've been given this key for an elliptic curve crypto -system: A:=4569782456273849 B:=74578265973825694738 p:=164516845864567592349187678956932587156973824569837657473 So the EC group is ...
0
votes
0answers
22 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
16 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
1answer
20 views

Confusion about negligible and non-negligible functions in crypthography

I am learning basic cryptography from Coursera's cryptography I course and am a bit confused about the negligible and non-negligible function epsilon and how it relates to the predictability of pseudo ...
1
vote
0answers
23 views

Tidy way to represent XOR over the ring of $2^{32} - 1$

I was reading about a cipher called Speck, which defines a system of equations using Addition Mod $2^{32}$ ($\boxplus$), Bit Rotation, and XOR. If we pretend that the additions were taken over ...
0
votes
1answer
32 views

Square Roots in Number Theory

Let N=pq, with p and q primes, with p congruent to 7 mod 8 and q congruent to 3 mod 8. We have seen in class that if h is relatively prime to N, then h=efs, where e= 1 or -1, f= 1 or 2, and s=r^2 for ...
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 ...
2
votes
0answers
61 views

What minimum subset of fields of mathematics is needed to understand homomorphic encryption?

Without the luxury of full undergraduate training in mathematics, if one worked part time could the community list the smallest set of mathematical fields needed to understand homomorphic encryption? ...
0
votes
1answer
11 views

What exactly does it mean that the key $e \in \mathcal K$ uniquely determines $E_e$?

What exactly does it mean that the key $e \in \mathcal K$ uniquely determines $E_e$ ? Does it mean that for each $e \in \mathcal K$ there exist only one function $E_e$ corresponding to $e$ ? Does ...
0
votes
1answer
33 views

Cryptography Combinatorics question

I 'invented' this encryption device - take a string, and start with the first character. Swap this character with the second with probability $50$%. Move to the (now) second character, and repeat ...
0
votes
1answer
55 views

Number theory used in cryptography [duplicate]

I am entering the realm of cryptography and encountering Number Theory related stuff a lot (As expected). I have a good knowledge and background on mathematics but I have been away for a while. So if ...
0
votes
2answers
35 views

In (m mod n = x) how to find m when you know n and x?

So I'm doing some cryptography assignment and I'm dealing with a modular arithmetic in hexadecimal. Basically I have the values for $n$ and the remainder $x$, but I need to find the original number ...
1
vote
1answer
67 views

how to solve $x^2 \equiv a \pmod{ n}$, where $n = p_1 p_2 \dots p_r$

Let $p_1,p_2, \dots , p_r$ be different odd prime numbers, and $n$ be the multiplication of them $n = p_1 p_2 \dots p_r$. Let $$a \in \mathbb{Z} / n \mathbb{Z}$$ and assume that $\gcd(a,n)$ is ...
1
vote
2answers
24 views

Help with linear recurrence.

I am trying to understand the following problem: Consider the following linear recurrence over $Z_2$ of degree four: $z_{i+4} = (z_{i+3} + z_{i+2} + z_{i+1} + z_{i}) \bmod 2$ i >= 0. ...
0
votes
1answer
29 views

Who to solve this linear modular equation system?

I have this equation system: a + b + c (mod 11) = 8 9a + 3b + c (mod 11) = 2 16a + 4b + c (mod 11) = 9 Unfortunately I totally don't know how to solve it. It is in general part of Lagrange's ...
0
votes
1answer
27 views

Stream ciphers - Block ciphers

What is the difference between the stream ciphers and the block ciphers?? Is the difference the time complexity?? At the block ciphers the message is cut into parts of $n$ characters. If we have ...
3
votes
2answers
73 views

In cryptography, why do we reduce elliptic curves over finite fields?

What's wrong with real numbers? Is the continuous logarithm problem "easy" to solve for elliptic curves? Here's what I believe: elliptic curves over the real numbers have infinitely many points, many ...
0
votes
1answer
31 views

How many multiplications are needed when one applies the algorithm to computing $132^{1023} \mod 2047$?

Suppose the integer $a$ has binary representation $b_kb_{k-1}\cdots b_1b_0$ where $b_i$ are either $0$ or $1$. The power $x^a \mod n$ can be computed using the fast exponential algorithm. The ...
0
votes
2answers
54 views

Where does 2525 and 252525 come from in RSA cryptosystem example?

This is an example from Discrete Mathematics and its Applications I understand how to encrypt, the first step is to turn the letters into their numerical equivalents(same thing we had to do for ...
0
votes
1answer
20 views

How to recover the original text/find decryption function?

This is from Discrete Mathematics and its Applications Here's my book section on shift ciphers. I understand the idea behind this. If you were trying to encrypt say a single letter 'b' with a ...
6
votes
3answers
123 views

Is this proof for $(\mathbb{Z},+) \ncong (\mathbb{Q},+)$ valid?

In an introductory cryptography course, our teacher demonstrated a proof for $(\mathbb{Z},+) \ncong (\mathbb{Q},+)$. I'm not convinced, even though the statement may be correct (I don't know). ...
2
votes
1answer
45 views

Generating elements of a Galois Field using an irreducible polynomial

I am practicing some cryptography problems and I am having problems with one involving Galois Fields and irreducible polynomials. Here is the problem: Using the irreducible polynomial $f(x) = x^5 ...
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 ...
1
vote
1answer
47 views

Finding the Order of a group and the Order of each element

I am working on a cryptography example problem. The problem is the following: For the group G = < Z26*, x> a) find the order of the group b) find the order of each element in the group c) Is ...
0
votes
2answers
61 views

Function for encryption/decryption - What is $n \phi(n)$?

In my notes there are the following functions of encryption/decryption: $$E_k(x)=x+k$$ $$D_k(y)=y-k$$ ($E_k : \mathbb{Z}_n \rightarrow \mathbb{Z}_n$) ($D_k : \mathbb{Z}_n \rightarrow ...
1
vote
4answers
74 views

How to prove this modular multiplication property to be true?

I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90 Here is author's work In this problem, the author was trying to calculate $5^{40}$ He worked ...
0
votes
0answers
68 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. ...
1
vote
1answer
52 views

Suppose that you had a machine that could find all four solutions for some given $a$. How could you use this machine to factor $n$?

Question: Suppose $n = pq$ with $p$ and $q$ distinct odd primes. Suppose that you had a machine that could find all four solutions for some given $a$. How could you use this machine to factor $n$? ...
2
votes
1answer
53 views

Prove that if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, then it has four solutions.

Question: Suppose $n = pq$ with $p$ and $q$ distinct odd primes. Suppose that gcd($a,pq$) = 1. Prove that if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, then it has four solutions. ...
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
1answer
23 views

Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...
0
votes
1answer
17 views

Cryptographic encoding scheme that enables counting

Suppose there are $n$ players. Each player has a $k$-length bit vector. Is there an efficient way of encoding the $k$ length bit vectors, such that after receiving the $n$ encoded outputs, one can ...
1
vote
1answer
36 views

Proving that a set Rn (relatively prime with respect to any n) is a group

Question: prove that the set of all Rn (relatively prime with respect to any n) is a group ... there is a theorem that states Rn is a group for n > 0, but i dont know where that came from... (Just ...
1
vote
1answer
33 views

$a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even

Questions: Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that $a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even. ...
0
votes
1answer
52 views

Given an encryption key in a transposition cipher, find the decryption key

I am continuing my practice on problems for my cryptography class. I'm starting to get the hang of basic ideas of ciphers. At least i thought this until I attempted to do the follwng problem: The ...
1
vote
1answer
24 views

Finding all the solutions of a linear equations

I am trying to find all the solutions to the following equation: $5x \equiv 15\pmod{25}$ Here is what I've done: Find the $\mathrm{gcd}(5,25) = 5$; there will be $5$ solutions. Divide the original ...
2
votes
0answers
34 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
1
vote
1answer
58 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...