Questions tagged [cryptography]

Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).

Filter by
Sorted by
Tagged with
1
vote
0answers
8 views

equivalent sub-keys in DES encryption

i am trying to understand the DES cryptosystem and was wondering: what would've happened if all of the sub-keys were equal? does it reduce the security? can we actually find the keys if we know all ...
1
vote
1answer
22 views

Period of sum of two periodic sequences

I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ ...
2
votes
1answer
15 views

Determining key from plaintext and ciphertext (Vigenère)

I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.
0
votes
0answers
31 views

Is 'the bombe' technically a computer?what is technically meant to be a computer?

Some say that 'the bombe' created by Alan Turing is technically not a computer despite decrypting the codes. Why is it so? Is 'the bombe' technically a computer? First of all what is technically ...
3
votes
1answer
20 views

Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
2
votes
2answers
46 views

If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear ...
0
votes
1answer
15 views

Cryptography: Play Fair cipher

In our university, we were taught that since all 26 letters cant be placed together in a $5*5$ square matrix we must put $i/j$ together like this represented in the below diagram. Here our key is $...
0
votes
1answer
41 views

Diffie-Hellman and its disadvantage with large primes

I was reading our university slide on the Diffie-Hellman where it is mentioned that one of the disadvantages of D-H is that For large prime, $p-1$ is an even number so, $\mathbb{Z}^*_p$ will have a ...
0
votes
2answers
41 views

What are the elements of the modular ring mod 7? [closed]

Are the elements of a modular ring simply the set of all the numbers from 1 to p−1? in this case p−1 = 6 ? I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was ...
1
vote
1answer
21 views

Weaknesses arising from using same key in both channel directions

I came across the following question: Which of the following risk may arise, when same key is used to encrypt both directions of a communication channel, that are not present if using different keys ...
5
votes
1answer
64 views

Perfect Probabilistic Encryption still requires key length about as long as message

Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E_k$) and $n+10$-length messages. Then, show that there ...
1
vote
2answers
42 views

RSA cryptosystem: Encrypting a signed message

I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message. If Bob wants to send a message $M$ to Alice:...
1
vote
1answer
24 views

Underlying codes for Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d := min\lbrace k \text{ such that there are $k$ linearly ...
1
vote
0answers
66 views

A tree-like data structure with rights delegation for distributed computing

Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
3
votes
1answer
72 views

Is F(F(s,x), x) necessarily a PRF if F is?

Given a PRF - F, is $G_s(x)=F_{F_s(x)}(x)$ necessarily a PRF? First I thought how to tackle this problem. First I tried using a hybrid argument: $|\mathbb P[F_{F_s(x)}(x)] -\mathbb P[f(x)]|\leq |\...
1
vote
0answers
63 views

Inverting a function [closed]

I posted this question on mathoverflow two years ago but got no answer: Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$ Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-...
2
votes
3answers
1k views

Is time complexity more important than space complexity?

I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it ...
2
votes
2answers
53 views

Why don't most websites I visit seem to use TLS with Ephemeral Diffie-Hellman?

When I click "view certificate," under Public Key Algorithm it usually says "RSA Encryption" or "Elliptic Curve Public Key." I assume this is the algorithm used to agree on a premaster secret (...
1
vote
1answer
25 views

Why does Feistel encryption algorithm encode half block every time?

Why does Feistel encryption algorithm encode half block every time? What would happen if the entire block is encrypted in each step?
10
votes
2answers
795 views

Can you prevent a man in the middle from reading the message?

I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the ...
-1
votes
2answers
49 views

Finding small-length RSA private key

I was wondering if there is an algorithm to derive $p$ and $q$ or is it simply trial and error? Consider the following RSA crypto-system with public key $(437,13)$. Since the numbers are so small, ...
1
vote
0answers
36 views

Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
1
vote
1answer
123 views

Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not. Is $z = x \oplus y$ uniform?
1
vote
1answer
31 views

DES encryption - what happens if all sub-keys are the same?

What will happen if we change the DES encryrption algorithm to use the same key in each round ? How will it affect the encryption - will it only make the encryption same as decryption or are the more ...
1
vote
1answer
66 views

Prove hash family is 3-wise independent

Let $q$ be a prime number and let $\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$; I need to prove that the family $\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \...
1
vote
1answer
80 views

fully homomorphic encryption with information-theoretic security?

An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can ...
3
votes
1answer
56 views

Anonymous Visibility Check in P2P networks

I'm working on a problem for a P2P network for games. The problem is the following: Consider two opponents on a grid, each stores it's own position. Player 1 wants to know if it sees player 2. In ...
1
vote
1answer
46 views

Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an “e” value and a “n” value?

I have a ciphertext $c$ encrypted with RSA algorithm that needs to decrypt. I have the public key $(n,e)$. Is it possible to decrypt with this amount of information?
4
votes
1answer
163 views

Any evidence that one way functions exist?

There is no known proof that one way functions exist. But what is the heuristic evidence that they exist? I sometimes read that the existence of cryptography is heuristic evidence that they exist. E....
0
votes
1answer
21 views

Is it possible to give a guarantee about the accuracy of the local time?

Assuming there is no attack/bug and I use NTP: Are there any formal guarantees about the accuracy of the local time? Can there be any over the network? Even if the communication is going directly ...
0
votes
1answer
56 views

Interchangeable role of public/private key pair and encoding/decoding algorithms

In designing a public-key cryptosystem, there are often two desirable properties: Public/private key pair of each participant can be exchanged. Meaning that whenever a participant has generated a key ...
4
votes
0answers
102 views

Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
4
votes
1answer
142 views

Why is fully homomorphic encryption so slow?

What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times ...
1
vote
2answers
50 views

Can the program determine the frequency of the CPU or is it impossible?

In order to understand the question, imagine a simple situation. Alice tells Bob that her CPU's frequency is X Hz. Bob does not take her word for it. Bob can not meet with Alice and check what ...
0
votes
2answers
20 views

How does storing encrypted password provide secure authentication?

It's universally accepted that storing an unencrypted password for automated authentication is a very bad idea, for the saved password can be used by malware, etc. There is a number of systems that ...
4
votes
1answer
41 views

How to make smart contracts work in a small network?

Suppose we have a small computer network, there are 30 random people who have provided their computers to perform any computational tasks on them. Let's call these 30 computers nodes. We can access ...
2
votes
2answers
27 views

Proof of non-receipt of the file

The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested ...
0
votes
1answer
51 views

Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$? $$h : S^* \rightarrow \mathbb{N} $$ Assume $S$ is finite. I would prefer an ...
0
votes
1answer
66 views

Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} ...
2
votes
1answer
64 views

Finding $d$ in RSA Encryption mathematically and by hand

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically. Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively ...
7
votes
3answers
2k views

Problem with the pseudo random number generator One-Time-Pad

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
3
votes
1answer
80 views

Trustless exchange without a third party

Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other?...
0
votes
2answers
55 views

What's the correct term for this analog of cryptography?

Suppose there is a communications channel between two parties. Suppose I want to send information through this channel, but I want to make it look like noise. Ie, I don't necessarily want to encrypt ...
4
votes
2answers
79 views

Blockchain cipher suitable for preschoolers

Is there a cipher that well suited for preschool-aged children to work out on pencil and paper, to learn concepts of block chains? It must have the following requirements: Able to be easily verified ...
3
votes
1answer
385 views

Computation of discrete logarithm

I know that an equation $$a^x \equiv b \pmod{p}$$ can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as ...
1
vote
1answer
54 views

Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven'...
4
votes
1answer
86 views

Prove complexity bound without reduction?

The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the ...
0
votes
1answer
34 views

Can SSL be hacked if we know some of plain data?

As I know, SSL/HTTPS is two stage, first stage is public key encryption/decryption which transfers key of the second stage which is symmetric. It is true we don't have key, but we can have some of ...
1
vote
0answers
49 views

eVoting with Damgard-Jurik-Cryptosystem

I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible ...
1
vote
1answer
156 views

Understanding the Bitcoin White Paper's Notion of “Signing” and “Verifying”

Consider from the Bitcoin white paper a graphic that includes dotted arrows, labeled "sign" and "verify": What does it mean to "sign" and "verify", as outlined in this paper? Are the terms "...