texts: Obliviously computing the Least common multiple of two poylnomials

texts:
Consider I have two polynomials $f_1$ and $f_2$ of the same degree. I want to secure them (using any kind of encryption except FHE) and outsource them to an untrusted server. I want him to compute the least common multiple (LCM) of these two polynomials and return it to me.

Question: Is there any protocol supporting above scenario ?

Or

Consider a more simpler scenario:

I have $C_1= a\cdot b \bmod p$ and $C_2=a \cdot d \bmod p$, where $p$ is a prime number. I want to outsource $C_1$ and $C_2$ using any form of encryption (other than FHE) and want to delegate GCD computation on these two values to a server without he knows the result (which is $a$).


texts: R, S, and Z values in a transaction using the Transaction ID

texts:
How can i get the R, S, and Z values and the Public Key using a transaction IDE i have?
I knew of a website called 2coin.org which provided these values but now the website is no more active and it seems that there are no websites that i could use to find that for me. any suggestions?


texts: Can `hash( messageA ) + messageB` be used to determine `hash( concat( messageA, messageB ) )`?

texts:
In .NET and other programming platforms all hash functions (such as MD5, SHA256, etc) can be used with streams of bytes, potentially forever - so it isn't necessary to read an entire multigigabyte file into an in-memory buffer to compute the hash of the file, the hash algorithm simply considers new data as it arrives and updates its internal state accordingly.

...it makes me think of the arithmetic Mean function which can work in the same way below, using C# IEnumerable<Byte> to represent a potentially infinite stream of data:

public static int Mean(IEnumerable<Byte> bytes)
{
    UInt64 sum   = 0;
    UInt64 count = 0;

    foreach( Byte b in bytes )
    {
        count++;
        sum += b;
    }

    return (Double)sum / (Double)count;
}

I've long assumed that hash functions might work in the same way as accumulators (warning: considerable over-simplification, I know there's more at work):

public static Byte[] SomeHashFunction(IEnumerable<Byte> bytes)
{
    Byte[] hashState = new Byte[32];

    foreach( Byte b in bytes )
    {
        ConsiderByte( hashState, b );
    }

    return hashState;
}

With arithmetic-mean, provided you know the count and the mean so-far, then you can compute an updated average as new data arrives without needing to see all previous data. E.g. the high-school exam question "If the average height of 20 students is 157cm, and the 21st student is 181cm, what is the new average?" ( ( 157 * 20 ) + 181 ) / 21 == 158cm.

I'm assuming we can do the same for hash functions like SHA256, then SHA256( concat( messageA, messageB ) ) should be computable given SHA256( messageA ) and messageB separately.

But instantly I imagine there's some "final processing step" that non-trivial hash algorithms will do to prevent that (such as not processing individual bytes, but processing blocks of bytes and padding them to some amount if the input data isn't long enough (indeed, in .NET there's the TransformBlock function but also the TransformFinalBlock function so there definitely is special processing when the end of data is reached). This means that provided we can get the internal state of the hash function after processing messageA and persist it then we can compute hashes of concatenated messages. Are there any weaknesses in any algorithms like SHA256 where the internal state can be derived from the output? Is this a weakness at all? What techniques can be used to prevent the internal state being derivable from the output?


texts: What is the purpose of placing the most significant byte first?

texts:
When the SHA algorithm states "A block of 128 bits is appended to the message. This block is treated as an unsigned 128-bit integer (most significant byte first) [emphasis added] and contains the length of the original message (before the padding)[,]" what is the purpose of placing the most significant byte first?

For example, if we have an integer of 24, which would be 00011000, and we therefore need 15 bytes of 0's to complete our 128-bit block, does this mean that 00011000 comes first followed by 15 bytes of 0's? It seems like this must be what they're saying.

I'm just confused why this byte needs to be first...

Source: Network Security Essentials (6th ed), William Stallings, p. 72


texts: Size of IV in AES-GCM according to RFC 4106

texts:
RFC 4106 specifies about nonce. It contains a salt of size 4 octets and an iv of size 8 octets. Further, RFC specifies that salt is assigned at the beginning of the security associations which is established through Internet Key Exchange (IKE) and salt value is constant. But all most all of the implementations and descriptions found about AES-GCM specifies iv as 12 octets and there is no consideration of salt value.

AES-GCM takes inputs as a secret key, an IV, a plaintext and Additional Authenticated Data (AAD). AES-GMAC is a variant of AES-GCM which provides authentication of data by keeping plaintext as zero bits.

Other questions I have regarding AES-GCM mode are.

I know that AES-GCM can be used for authentication of data by Can we use AES-GCM mode only for encryption by ignoring authentication?
Is it mandatory to use iv for encryption using AES-GCM?
What are the allowable variants of AES-GMAC like AES-GMAC128, AES-GMAC256 etc. ?


texts:
What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\le m\le n$) are necessary to reconstruct the secret, and less than $m$ shares reveal no information about $K$.

For $m=n$ (e.g. 2-out-of-2), we can use $n-1$ shares $S_i$ ($1\le i<n$) of uniformly random independent bits, and another $S_0$ that is the bitwise-XOR of the secret $K$ and the other shares: $S_{0,j}=K_j\oplus\left(\displaystyle\bigoplus_{i=1}^{n-1}S_{i,j}\right)$. The secret is recomposed by bitwise-XOR of the random shares: $K_j=\displaystyle\bigoplus_{i=0}^{n-1}S_{i,j}$.

This is easily extended to $2^k$ symbols, e.g. octal or hexadecimal.

For 2-out-of-3, we can use a ternary system, a first share $S_0$ of random trits, an two shares $S_i$ ($i\in\{1,2\}$ ) defined by $S_{i,j}=S_{1,j}+i\,K_j\bmod3$. The secret can be recomposed from any two shares, as:
$$K_j\,=\,S_{1,j}-S_{0,j}\bmod3\,=\,S_{2,j}-S_{1,j}\bmod3\,=\,S_{0,j}-S_{2,j}\bmod3$$
The tables for addition (used for encoding) and subtraction (used for decoding) are:

    | 0 1 2                             | 0 1 2
----+------                         ----+------
+ 0 | 0 1 2                         - 0 | 0 1 2
+ 1 | 1 2 0                         - 1 | 2 0 1
+ 2 | 2 0 1                         - 2 | 1 2 0

This is easily extended to base $3^k$; e.g. for $k=2$

    | 0 1 2 3 4 5 6 7 8                 | 0 1 2 3 4 5 6 7 8
----+------------------             ----+------------------
+ 0 | 0 1 2 3 4 5 6 7 8             - 0 | 0 1 2 3 4 5 6 7 8
+ 1 | 1 2 0 4 5 3 7 8 6             - 1 | 2 0 1 5 3 4 8 6 7
+ 2 | 2 0 1 5 3 4 8 6 7             - 2 | 1 2 0 4 5 3 7 8 6
+ 3 | 3 4 5 6 7 8 0 1 2             - 3 | 6 7 8 0 1 2 3 4 5
+ 4 | 4 5 3 7 8 6 1 2 0             - 4 | 8 6 7 2 0 1 5 3 4
+ 5 | 5 3 4 8 6 7 2 0 1             - 5 | 7 8 6 1 2 0 4 5 3
+ 6 | 6 7 8 0 1 2 3 4 5             - 6 | 3 4 5 6 7 8 0 1 2
+ 7 | 7 8 6 1 2 0 4 5 3             - 7 | 5 3 4 8 6 7 2 0 1
+ 8 | 8 6 7 2 0 1 5 3 4             - 8 | 4 5 3 7 8 6 1 2 0

See this for $k=3$ used for the 26 letters and space.

As long as conciseness of the shares is not an issue, we can directly encode binary with the ternary system, octal with $k=2$, hex with $k=3$, base64 with $k=4$.

What about other $m$-out-of-$n$ schemes? In particular 2-out-of-4, 2-out-of-5, 3-out-of-4?


texts: After Google's breakthrough: When will quantum computers break today's encryption?

texts:
Google announced a breakthrough on the way to building usable and useful quantum computers.

Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.

Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?


texts: Security of SRP-6a against impersonating server choosing small/wrong N

texts:
I'm looking at an implementation of SRP (Secure Remote Password) that essentially follows the Stanford documentation (http://srp.stanford.edu/design.html). I'm worried about one aspect though: In the initial message exchange the server sends the parameters to be used (modulus $N$, generator $g$, salt $s$) to the client after potentially looking up these parameters per user.

A correct server would choose $N$ as a large safe prime and $g$ as a generator. Under these circumstances I can see why the further protocol will give no information to try more than one password per protocol execution to a) a passive attacker, b) a man-in-the-middle attacker, or c) an active attacker that impersonates a server but doesn't have a copy of the server's database of password verifier values (otherwise a brute-force attack is trivial).

However, given that the attacker is not likely to play by our rules, what would happen if an attacker that impersonates a server (but doesn't know the password verifier stored in the server database) choose bad values for $N$ and $g$?

These could be

small $N$
composite $N$
non-safe prime $N$
generator $g$ of a small subgroup in composite or non-prime $N$

Wouldn't the attacker in the server's position then be able to brute-force the discrete logarithm and learn the password-equivalent secret $x$ modulo their chosen small $N$ or in a small subgroup?


texts: Differential privacy basics: Universe \mathcal{X} and database $x$

texts:
The "Algorithmic Foundations of Differential Privacy" book (DOI: 10.1561/0400000042) introduces formally the "universe" and "database" on page 17 roughly as:

$\mathcal{X}$ is a universe
databases $x$ are collections of records from the universe
For convenience, we use histogram of types from the universe $\mathcal{X}$ to represent $x$, such that: $x \in \mathbb{N}^{|\mathcal{X}|}$ where each entry $x_i$ represents the number of elements in the database $x$ of type $i \in \mathcal{X}$

If you take the example from Wikipedia

The universe $\mathcal{X}$ is a set $\{0, 1\}$?
The database $x$ is

a vector [3, 3] (assuming the universe is ordered)?
or a map {0:3, 1:3}?

My two questions are:

Is my understanding correct?
Why is it "convenient" to do so? What would be the non-convenient alternatives?


texts: Preimage attack given half of the preimage

texts:
512 bit X has been hashed using SHA256(X) = Y

Given Y and half of X (the first 256bits) to attacker, how hard is to reveal whole X
Can SHA256 or any real world function be cracked to allow this problem to be solved faster

Is this problem known in cryptography? and under what name? Tried google for concatenated preimage attack but found nothing.


texts: How to find m so that RSA cipher end with '\x00'+SpesificString , if we freely input the plaintext?

texts:
I have an RSA encryption with public key $(3,n)$ with 2048 bits modulus $n$.
I want to find the value of the plaintext $m$ so that the ciphertext (in bytes representation) value ends with \x00+MySpesificString.
$ciphertext = pow(m,e,n)$
where $m$ can be any string and ciphertext has the following format
any string+\x00+MySpesificString
How I can find the possible value of $m$?


texts: How is the keystream actually generated in AES CTR

texts:
I've been trying to find out how the keystream in AES-CTR is generated, but I can't actually figure it out. Wikipedia and any other sites that "explain" it just say the nonce is padded with the counter and encrypted with the key...

So how does it actually work? (As nitty gritty as possible please)


texts: Bent functions are boolean functions with maximum nonlinearity and are widely studied for their potential applications in cryptography. Lets say you wanted to use a simple two input AND gate as a nonlinear combiner for the outputs of two Linear Feedback Shift Registers . Because a two input AND gate is a bent function, is it technically correct to call the output sequence of this combination generator a bent sequence ( I need to know this for a paper I am writing).Thank you for commenting.


texts: Use additional keys to thwart key compromise?

texts:
Is it good or bad practice to design crypto protocols for key compromise by using additional keys? Argument for bad practice would be: When you have a key you should trust it and not throw more keys at the protocol "just in case". Is there any research/substance to that argument? Eventually, does it all boil down to a risk analysis (cost of compromise vs cost of additional keys)?

A small example to illustrate my question:

Assume Alice and Bob regularly communicate with each other using encrypted (using symmetric $K_{enc}$) and authenticated (using symmetric $K_{auth}$) messages:

$Cryptotext = Enc(K_{enc}, msg)$
$Alice \rightarrow Bob: Cryptotext, Hmac(K_{auth}, Cryptotext))$

Very rarely they want to communicate messages $M$ whose integrity is extremely important.

Under which circumstances (if any) would it make sense to use a second $K_{auth-important}$ to protect these extremely important messages?

$Cryptotext_M = Enc(K_{enc}, M, Hmac(K_{auth-important}, M))$
$Alice \rightarrow Bob: Cryptotext_M, Hmac(K_{auth}, Cryptotext_M)$

A motivation might be that since $K_{auth}$ is used in all communication it is more exposed and at least theoretically more likely to become compromised by recording and analyzing traffic. However, the protocol becomes more complex and if burglar Bert breaks into Alice's or Bob's safe, he will still find $K_{enc}$, $K_{auth}$ and $K_{auth-important}$.


texts: Where can I find a versatile PKI and library leveraging curve25519?

texts:
I note that Things that use Curve25519 provides a long list of protocols, software, and libraries that leverage curve25519, but I'm wondering if there is any such software that more fully implements a self-contained PKI ecosystem?  For example, implementing the ability to generate a certificate and distribute it - perhaps in some kind of hierarchical chain of trust.

Which of the projects out there might be closest to providing that?  Perhaps it's one from that list, or maybe it's another PKI system that could use curve25519 (and poly1305-AES/Salsa) as its algorithmic foundation.  For my question, I'm looking for versatility (such as being able to distribute keys or update keys in a way that's authenticated), but I don't necessarily need too much complexity.  However, answers can freely be shared which follow slightly different criteria.


texts: Forgery attack for Merkle–Damgård MAC scheme with prefix method

texts:
Consider a hash function $H$ based on an iterated hash function $H_0$
  with $l$-bit block messages an the Merkle–Damgård strenghtening pad.
  That is, $m||pad(m)$ has a length multiple of $l$ and $H(m)
 =H_0(m||pad(m))$

  We consider the MAC algorithm defined given a $l$-bit secret key K and a
  message m as $MAC_K(m) = H_0(K||m||pad(m))$ where || denotes the
  concatenation operation.

  Show that given the MAC of a known message m the adversary is able to
  output a forgery on a message $m' \neq m$

The solution of the exercise forges MAC for message $m′ = m || pad(m) || m^⋆$
for arbitrary $m^*$. It hashes $m^*$ and uses $IV = MAC_K(m)$.

The problem is that I don't understand how this scheme works. First, what is the $f$ function of the drawing? Is it $H_0$? But then how is it that it is taking two parameters, namely, and $l-block$ and an IV? Also, can you do some math that show that this construction works?


texts: What would a backdoor in symmetric key cipher look like?

texts: Pretty much what the title says. DES was suspected of having one, but I couldn't imagine what it could possibly look like if only the NSA knew how to use it. Dual_EC_DRBG's backdoor is asymmetric, but it's not a cipher. Could one have a kletographic symmetric key cipher?


texts: Is there a way to compress multiple signatures of the same data?

texts:
So, I'm working with a system that allows individual users to each have their own private-public key pair.

I would like to allow multiple users to use their private key to sign the same piece of information to confirm they agree with something.  By signature, I mean the public key can be used to check the signature is valid.

However, space is at a premium.  So is there a way to compress those multiple signatures of the same data?

Using Curve25519, but other algorithms might be acceptable.


texts: How can I share a number with an opponent?

texts:
Let's say I have a message (eg: Hello, world!) and I want to encrypt this message using symmetric encryption (AES-256). I am using a list of keys, where I randomly take one as a key (so that each message has a random key). My opponent also has this list of keys, but due to its size it will take too much time to brute-force.

I would like to somehow share either the key, or the index number of the key in the key-list with my opponent, but I have to do it at the same time I am sending the message.

Is there an algorithm or protocol which I can use to handle this scenario?


texts:
I've read a lot of information about PRNGs, PRFs and KDFs. As far as I know:

PRNG: The seed for the PRNG must be a uniform string. It transforms a short real uniform string into some bits of pseudo-randomness.

PRF: The PRF gets a uniform key and some additional input and transforms it  into a string of pseudo-randomness.

KDF: For example the HKDF scheme uses the hmac as PRF and does not need any uniform input string. It generates some pseudo-randomness.

So far, is that right? I would like to get some additional information about literature on that topcs, in particular further on the inputs of PRF and KDF.


texts:
We have some simple PRNG, like a LCG or LFSR. Easiest is one that follows a output state, transform state cycle. Let's call that cycle an "iteration", and one of these outputs a "word".

Knowing the PRNG used, and all parameters including the starting state, we want to take a given word, and assuming it does appear in the output sequence, find the "index", that is, the number of iterations before that word appears for the first time.

Of course, this problem will vary between PRNGs, but what I want to know now is:

How hard is it in general? $O(2^n)$ for $N$ bit words, or much less?
Which PRNGs, if any, is it easy for? Looking for polynomial to $N$, or at least subexponential.
How to detect when the given word doesn't appear in the output sequence, when it's not obvious like with a LCG.
What to do with PRNGs which output only part of their state or put it through some mapping (not a crypto hash of course).

Plain LCG would be harder than discrete logarithm right? Discrete logarithm is doable in polynomial time for power of 2 modulus though. Not sure how much difficulty the addition adds.

I'd think enough nonlinearity would make this task intractable due to the complexity. So ones like xorshift and MT19937 should be doable.


texts:
Protocol: Coin Flipping over telephone

Hypothesis:

Alice and Bob have agreed:

a one to one function $f$ which is easy to compute $f(x)$ from $x$ and while given any value $f(x)$ it is nearly impossible to find any information about $x$.
an even number $x$ in $f(x)$ represent HEAD and the other case represents TAILS.

STEP:

Alice picks a large random integer $x$ and compute $f(x)$; she reads $f(x)$ to Bob over the phone;
Bob tells Alice his guess of $x$ as even or odd;
Alice read $x$ to Bob;
Bob verifies $f(x)$ and sees the correctness or incorrectness of his guess.

Objectives:

Calculate the uncertainty of Alice.
Let $n=pq$, where $p$ and $q$ are distinct primes. Can $f(x)=x^2\mod{n}$ be used in protocol above? Please give your reason to support your answer.

My try:

Alice is sender. Plain-text, $x\in P$
Bob is receiver. Cipher-text, $C$
$f(x)$ is encryption function.

$\therefore$ The uncertainty of Alice is $H(P)=-\sum_{x\in P}Pr(x) \log_2{Pr(x)}$?
Yes, because it is one to one function?

Am I correct? Please help me, thank you.


texts:
Consider the pairing $e: G_1*G_2 \to G_t$.

Why we are mapping element from group $G_1$ and group $G_2$ to an element in $G_t$.
How are they used in cryptography?
What advantages do they provide?


texts: Why is D_K only required to be infeasible to derive from E_K for almost every key K?

texts:
In DH76 'New Directions in Cryptography', it states that

  3) for almost every $K \in \{K\}$, each easily computed algorithm equivalent to $D_K$ is computationally infeasible to derive from $E_K$

($E_K$ and $D_K$ means an encryption and decryption algorithm with key $K$, respectively.)

Then, why 'almost every', and not just 'every'?


texts: Why would using a random seed with other variables be bad for ecrypting if you can't guess the key?

texts:
I asked this on stack exchange with it being code based, but someone suggested to ask here.

Basically, I've done a script in python and wanted an option to encrypt the input, but I couldn't get any libraries working so I decided to try make my own, despite not knowing how actual encryption works. The result I think still needs a few tweaks, but I don't understand how it could be cracked.

I know the random feature of python is apparently very bad for encryption, but I'm using other things too, so you can't just fake an md5, you also need the exact same results from looping through each letter in the key.

I'll break it down into stages as to what it does:

  Step 1:Get md5 of the key and set that as the seed (it could be
  more complicated than an md5 but I don't think it'd make much
  difference

  Step 2:Loop through the key one letter at a time, and for each
  letter, crc32 it, and select one random digit from the result. Repeat
  this until you have x numbers (currently set to 128), and then shuffle
  the list.

  Step 3: Based on the size of the key, calculate how many extra
  characters to add for each character in the input. For all
  characters, generate another number between 0 and 255 to add to it.

  Step 4 (reverse all this to decode): Loop through the input one letter at a time, convert the
  character to a number, and add on the results from step 2 and 3,
  before converting back to a new character (making sure it is in the range of 0 to 255). The result is then all of these
  characters together, and can be reversed if the right key is given.

So, here's what the output is like:

key = "super secret key"
input = "Test!"

(encode)
Result: hxrBVvYX27YlyKWKMxrA

key = "super secret key"
encodedstring = "hxrBVvYX27YlyKWKMxrA"

(decode)
Result: Test!

key = "Super secret key"
(decode)
Result: ýO¼É

As you can see, the result is dramatically different when a lowercase letter is swapped for a capital, but it still comes out with something. In what way is this really insecure? The only way I'd know how to break it is by just trying millions of combinations until it finds an output word that's in the dictionary.

Also, as an example of it in use, I got it running here: http://goo.gl/VBRYpfHit the execute button, click in the green box, and follow the instructions :)

Apologies if it's not a suitable question for the website anyways, I'm not sure if I worded it a bit too specifically for my case


texts: Is it possible to find the product of two numbers without knowing the two numbers?

texts:
I'm doing a thought experiment:

Alice chooses a number $a$ and Bob $b$. They send $A(a)$ and $B(b)$ to Charlie. He performs $C(A(a), B(b))$ and gets $ab$.

Do there exist not easily reversible functions $A, B, C$ for which the above is true?

I'm a beginner so I'd be all the more grateful if somebody knows :)

Thank you!


texts:
What are the positive consequences for choosing 8 S-boxes for DES vs 1 S-box for AES?

I could guess side channel resistance, but I can't find anything on it.


texts: Can a cryptographic hash be used as a cryptographic RNG?

texts: Say I roll a six sided die 200 times (6^200 = ~2^517) and string all the results together into a long string of numbers and hash then result with SHA-512. Can I use that result for cryptographic purposes such as keys? Can I then use the hash of that result to generate more keys?


texts: Homomorphic Encryption operation for regression

texts:
I must be missing something, and I am sorry if this is a novice question...

I have seen in places (eg. https://crypto.stanford.edu/~dwu4/talks/SecurityLunch0214.pdf page 13) that linear regression is possible on the cipher text of a fully Homomorphic Encryption system.

My question is:
if you can generate the inverse of the matrix (X^T X), then can't you generate the cipher version of the identity matrix, and determine what E(1) is? And if you have E(1) can't you generate E(2) ... E(n) using either encrypted addition or plain text multiplication?


texts: Why BouncyCastleAesCbcBytesEncryptor is using a salt and an initialization vector?

texts:
I'm using the class BouncyCastleAesCbcBytesEncryptor from Spring Security. One of the constructor has the following signature:

BouncyCastleAesCbcBytesEncryptor(String password, CharSequence salt, BytesKeyGenerator ivGenerator)

I was first thinking that salting is not necessary with AES, my first idea was confirmed by this accepted Stackoverflow answer:

  Salting is generally something that is done when hashing a password, not when encrypting plaintext; for example, you would use a salt when generating a key from a password using PBEKeySpec. AES's "salt" is its initialization vector.

My question is: why does this constructor ask for a salt AND an initialization vector generator?


texts:
We want to generate coupon code series and then encrypt those coupon code in numeric only, and that must also be decipherable.

We will be sharing encrypted code as coupon code with customer.

These are the conditions:

Encrypted code must not be in series or not easily able to guess;
Encrypted code must be numeric.
Encrypted code must be having a specific number of digits (think: size/length).

Example :

We generate coupon code from 1 to 100 (needs in millions and plainCode will be either numeric or alphanumeric doesn't matter).

We want share encrypted numeric coupon code with specific digits to user.
i.e. if code is 52 then encrypted code gives us between 10000 to 99999 (if 5 digits are specified or it need to be fix number of digits)

We are also able to decrypt the same.

Note:

Above is just an example. possibilities are in millions.
Security is not a major concern. just not able to guess is matters a lot.
encrypted code must be in numeric.

Question:

Is there an established, cryptographical secure way to do this? If not, what would we need to do to handle this?

Any suggestions or ideas are more than welcome.

We have looked and FPE. Any good algo for the same recommended which return in specific number of digits. We have one which gives encrypted numbers less than specified number but we want in between specific range to maintain number of digits without 0 appending.


texts:
I'm studying about Additive differential of XOR

I saw two papers that are "H.Lipmaa et al., On the Additive Differential Probability of Exclusive-or" and "V.Velichkov et al., The Additive Differential Probability of ARX"

In this two paper, Limaa et al. and Velichkov et al. compute the probability of additive differential of xor in similar way.

But there is one difference between them.

That is matrix $A_i$ is different.

For example $A_{000}$ in first paper is  $A_{000}=\begin{pmatrix}
4& 0& 0& 1& 0& 1& 1& 0
\\0& 0& 0& 1& 0& 1& 0& 0
\\ \vdots & &  & \cdots & \cdots  & & & \vdots
\\ 0& 0& 0& 0& 0& 0& 0& 0
 \end{pmatrix}$

and $A_{000}$ in second paper is  $A_{000}=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0
\\0& 1& 0& 0& 0& 0& 0 & 0
\\ \vdots & &  & \cdots & \cdots  & & & \vdots
\\ 0& 0& 0& 0& 0& 0& 0& 1
 \end{pmatrix}$

I hope someone can tell me why there exists a difference.


texts: Help with next step in the Quadratic Sieve

texts:
So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here:

Say, for N = 90283, I compute bound =(12+(1))(ln()ln(ln√))=44, where I take (1)=0.22 (just a random guess, I assume). What is the best way to pick good (1)?

Then I take =⌈$\sqrt{n}$⌉=301

Then using Sieve of Eratosthenes I get a list of primes < :

{2,3,5,7,11,13,17,19,23,29,31,37,41,43}

Then by computing Jabobi (Legendre) symbol for each value in the primes list, I pick the first quadratic nonresidues to get factor base:
{2,3,7,17,23,29,37,41}

Then using the Tonelli-Shanks algorithm I compute modular roots ±, where  is a solution to $^{2}$ ≡  (mod ) with  a prime form factor base.

Then I get two arrays of solutions 1 = − (mod ) and 2 = −− (mod ), with p's from factor base. and also get one arrays of logarithms for p's  = ln rounded up to some precision, say two decimal digits. What is a good precision?

sol1 ={0,0,2,13,11,26,10,28}

sol2 ={0,1,5,14,8,10,17,26}

 ={0.69,1.1,1.95,2.83,3.14,3.37,3.61,3.71}

Now as far as I understand I have to initialize 'sieving_array' initialized to 0's, say, to size = 60 elements. Also, how should I choose size of the sieving interval? Is there any formula similar to the bound?

Then I have to add values from  to sieving array to positions 1[]+∗factor_base[j] and 1[]+∗ factor_base[j], where 0≤≤ size and 0≤≤|factor_base|. And for prime =2 add  only to positions with sol1. So I get this list (rounded to two decimal digits):

SieveArray ={1.79,1.1,2.64,1.1,1.79,1.95,1.79,1.1,3.83,3.05,8.77,3.14,3.74,3.93,3.52,1.1,3.74,3.61,1.79,3.05,0.69,1.1,1.79,1.95,1.79,1.1,9.72,1.1,5.5,0.0,6.57,7.07,0.69,3.05,4.93,0.0,1.79,3.05,0.69,4.47,3.74,0.0,1.79,1.1,2.64,1.1,1.79,8.39,4.62,1.1,0.69,3.05,1.79,0.0,10.49,4.47,0.69,4.24,3.74,0.0}

Now I am confused. The next step is(in Contini's paper) is to check each value is log(2x$\sqrt{n}$) but I don't get what x is. Also can someone please explain how to calculate the size and Sieving Interval?


texts: Using YubiKey to store a PIN-protected secret for disk encryption

texts:
I want to store a secret on YubiKey and use it for disk encryption. It's crucial that it be PIN protected. There are a limited number of PIN tries, and after three attempts the YubiKey would be blocked (self-destructed).

All the solutions I have found (like this one) are based on a HMAC-challenge-response YubiKey application which calculates SHA1-HMAC from the password and mixes the hash to/with the password. It protects against brute-force attack but not against rubber-hose cryptanalysis (waterboarding, etc.).

The problem is HMAC-chal./resp. is not PIN protected, and it seems YubiKey can't store a PIN-protected secret directly.

I found and implemented two solutions based on PIV.

I generate a new RSA 2048-bit key on the secret slot, use the key to encrypt a random secret and store the encrypted secret in the PIV-slot as an object. (certificate is usually stored there).
I have constant encrypted data ("constant data" means actually hardcoded "const char * data = {....3,5,87... }"). I generate a new RSA 2048-bit key on the selected slot. To obtain the secret, I just decrypt the constant data. I could sign the data and use the signature as the secret, but YubiKey mixes some random data into the signature, so it's not deterministic and can't be used.

To make it more secure, I could even drop the public key, so even the public variables of the key become unknown.

I'm convinced (1) is as secure as YubiKey is, but I'm not sure about (2). I like (2) much more than (1) since it doesn't use the objects for something which they are not supposed to be used for.

Is it OK to use RSA this way? Has anybody thought about similar YubiKey usage?


texts: What exactly means to sample from the set of congruence classes?

texts:
Say one is doing some cryptography around the set of congruence classes, namely: $$\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}_n = \{[0]_n, [1]_m, \dots, [n-1]_n\}.$$
Sometimes we use to write $a \leftarrow_R \mathbb{Z}_n$ to denote that we are sampling an element from $\mathbb{Z}_n$. But, what exactly means to perform such a sampling? I imagine that it is the following

Shorthand for $[a]_n \leftarrow_R \mathbb{Z}_n$ plus $a \leftarrow [a]_n$, i.e., taking the representative of the class, where $0 \leq a <n$.

Is it like that? We typically use this sampled number as an exponent, so it would not make sense to sample an entire congruence class.
At the begginning I though that $a \leftarrow_R \mathbb{Z}_n$ was writing to avoid writing $[a]_n \leftarrow_R \mathbb{Z}_n$ too many times. But it would not make sense.
It is also often to see that $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$. Is it a shorthand for its real meaning?


texts:
I've long been looking for a symmetric encryption scheme (or algorithm) with equivalent keys. Let me define what I want:

Symmetric encryption algorithm with encryption function $E_k$ and inverse decryption function $D_k$.
Existence of equivalent keys. Keys $k_i \neq k_j$ will be called equivalent if $E_{k_i}(\cdot) \equiv E_{k_j}(\cdot)$ as functions and the same for the decryption operation $D_{k_i}(\cdot) \equiv D_{k_j}(\cdot)$.
Without knowledge of some master secret, it would be computationally infeasible to derive an equivalent key $k' \neq k$ from a key $k$.
With knowledge of some master secret, it would be straightforward to derive at least "many" equivalent keys (let's just say that the equivalent keys should not be scarce compared to the size of the entire keyspace, e.g. 4 equivalent keys in the entire keyspace are not enough).
No trivial intermediate value: of course it's trivial to come up with a scheme satisfying all of the above in which all equivalent keys map to one intermediate value (for example take 128 bit keys with an additional 16 bits at the end, then discard these as a first step before applying standard AES-128). This is perhaps the most important feature and the hardest to define. Let's say then that it requires knowledge of some master secret or some special trapdoor to reduce equivalent keys to an intermediate value.

Does anyone know of existing schemes/algorithms satisfying at least most of the requirements above, or any interesting papers on the subject, or just have some bright idea to share with us?


texts:
I'm reading through Chow et al.'s paper and Link et al.'s paper.

There's a part I don't understand about Delinearization.

They convert some steps of AES/DES into a Matrix, then divide the matrix in 8x4 matrices and use look up tables to do the multiplications. But for the XOR they also use look up tables.

What is the use in that? It's pretty easy to see, even through a look up table, that we're doing simple XORs here.

PS: What I'm talking about can be seen here at page 30: http://summerschool08.iaik.tugraz.at/slides/Brecht_wbc1_crete_final.pdf


texts: Matsui's paper on linear cryptanalysis - unexplained formula in Lemma 2

texts: How does he end up with this result in his article ?


texts: How to exchange a secret through untrusted server in two steps?

texts:
I have a web application where I control the server, however, it should not have any knowledge of secrets that are exchanged between its users. This server holds RSA public keys of each registered user and can be trusted to deliver the correct public keys for each user when asked for them. A user's RSA public key is provided to the server whenever they register with the server. Users belong to "teams" and a user can only join a team by way of invitation from another already registered user that is a member of the team.

Alice is already registered and needs to invite Bob to her team and also deliver a team member secret to Bob. Bob is not registered yet, so Alice cannot ask the server for Bob's public key. Right now I have implemented this type of team member exchange where one user is registered while the other is not yet using a three step process:

Alice sends a team invitation to Bob.
Bob accepts the team invitation and registers with the server, providing the server with his public key.
Alice then asks the server for Bob's public key, encrypts the team secret and sends it to the server for Bob (who is now a member of Alice's team) to download.

Bob can now get the encrypted team secret from the server and decrypt it with his private key.

I am trying to reduce this team secret exchange to only two steps. Often times Alice will forget to come back and perform step 3 and would prefer to send the team secret in a secure way at the time of inviting Bob. This is simple to do if Bob was already registered with the server (the encrypted team secret could just be part of the invitation), but often times Bob is not yet registered.

Is there a way that I can perform this team secret exchange in a secure way using only two steps from the user? The server can be used as an intermediary to facilitate the exchange, but should not be able to read the secret.


texts: using different IV and SALT with AES-CBC but same KEY

texts:
I'm working on this project where a client can send a message, now obviously sending it in plainText is not very smart. So I decided to Encrypt it with AES-CBC.

Now, each time I encrypt something, the KEY is derived with PBKDF2, defined in RFC-2829, as:

DERIVED = PBKDF2(salt: 16 random bytes, key: plainText pasword, iteration count = 16834)

and this is the KEY. the IV is different every time BUT it's included in the final cyphertext.

Question: is it safe to use the DERIVED key , where the ORIGINAL key is the same, but the salt is different every time?


texts: Does RSA_PRBG security depend on keeping seed secret?

texts:
The HAC provides a PRBG using RSA (Chapter 5 p.185):

It appears the seed must be kept secret if $e$ is a well known value. If $e$ is uniformly distributed between 1 and $\phi$, then the seed does not need to be secret.

The first question is, are the observations of the seed correct?

The second question is, for second (and subsequent) random numbers, can step (1) be skipped. That is, can the RSA parameters be reused?


texts: I don't exactly know what I'm searching for but the scenario is at follows. Alice and Bob want to get married. According to the law, they have to make a set of medical investigations. Bob must show his medical results to Alice and Alice must show Bob her medical results. After that, they both need to go to a doctor that has to certify that they showed each other their medical results but the doctor isn't allowed to view the results of investigations from either Bob nor Alice. Can this task be resolved by a zero knowledge proof? If so, can you give me some references please? Thank you!


texts: How to prove properties of pre-image of random oracle in zero-knowledge proof?

texts: A signature Sig is given as input to random oracle H, such that y = H(Sig) and Sig should be hidden from the verifier. How to prove in zero-knowledge to the verifier that y is the correct output from a random oracle evaluated on Sig which verifies under some public key in a given set of public key while keeping the Sig hidden.


texts: What exactly could be accomplished with a backdoor in Dual_EC_DRBG?

texts:
Assume that some entity really holds the private key corresponding to the recommended/dubious constants of Dual_EC_DRBG.

According to this presentation, they would be able to reconstruct the internal state from only 32 bytes of random output and thereby predict all future output as well.

Would the backdoor also allow recovering previous output of the RNG, or does the
resistance against state compromise extensions still hold in that situation?


texts: Find out which keying option is being used in Triple DES?

texts:
As far as I know, there are three standard options for the three keys $K_1$, $K_2$ and $K_3$ used by 3DES:

Three distinct keys.
The first and last key are equal: $K_1$ = $K_3$.
Three equal keys: $K_1 = K_2 = K_3$

I wonder whether there is a way to find out which one of these options is (most likely) being used, given a set of known (plaintext, ciphertext) pairs. The attack does not need to reveal the keys; the goal is simply to find out which keying option is being used.

Currently, the only method I could think of consists of trying to recover the key. That is, apply known attacks on the third and second keying options. For example, a brute-force attack of complexity $2^{56}$ followed by a chosen plaintext attack of complexity $2^{57}$.

So the question is really: is there a way of doing this more efficiently, without having to figure out the keys. If that's not possible, (how) can the above mentioned method be optimized?


texts: In CBC mode of encryption, what happen if the IV is changed when it arrives at the receiver end?

texts:
What will happen if the Initialiazation Vector (IV), i.e, the initial randomness fed in to
the first block arrives mangled at receiver end? How will this affect the decryption? Will the receiver be
abl to decrypt all blocks correctly? Or none? Or some?


texts: Secure Secret Sharing to a Distributed Key

texts:
Setup
There are two groups, $A$ and $B$. Each group is in a Shamir's secret sharing scheme ($t_A$ of $N_A$ and $t_B$ of $N_B$). Each group has a public key that is associated with the identity of the group. The corresponding private keys are distributed among the members and are never reconstructed on any device. Each group has additional secrets as well. Every member has its own public/private key.
Problem
$A$ wants to share a secret to $B$, without reconstructing it and (assuming a threshold number of members in $B$ aren't compromised) without $B$ being able to reconstruct it.
If $A$ knows the scheme and the members of $B$, this is straightforward. $A$ performs a redistribution (like the one described in Verifiable Secret Redistribution for Archive Systems by Wong, Wang, and Wing), encrypting shares for each member in $B$. However, this is annoying because everytime the members or scheme of $B$ changes, $A$ needs to be informed of it.
Instead, $A$ can encrypt shares with $B$'s public key. In this case, how do the members of $B$ know that no member of $B$ can gain access to secret?$^1$
More concretely, there needs to be a group decryption operation for each share, with each decrypted share being available to a different member, such that no other member can see it.$^2$ The issue is assigning shares to different members in a way that replay attacks won't work, i.e., the entire protocol starting over with the same or a different set of $t_B$ members.
Replay Attack 1
Imagine a simple situation where $B$ is in a 2-of-3 scheme. Call the members $b_1$, $b_2$, and $b_3$. $A$ provides two shares in a 2-of-2 scheme, both encrypted with $B$'s public key. $b_1$ initiates the protocol with $b_1$ and $b_2$, gaining access to share 1. $b_1$ then initiates the scheme with $b_1$ and $b_3$, gaining access to share 2. So now $b_1$ knows the full secret without either $b_2$ or $b_3$ having approved of it.
Replay Attack 2
Now imagine a situation where $B$ is in a 2-of-2 scheme. $b_1$ initiates the protocol with $b_2$, getting access to share 1. $b_1$ initiates the protocol again, but this time gets access to share 2. In this application, the member initiating the protocol is the one who has access to the encrypted shares. The initiator provides the data to the other members, who do not have an independent way to get that data from $A$.

$^1$ More precisely, the honest members of $B$ don't want any group with fewer than $t_B$ members to be able to collude together to get the secret.
$^2$ This is a simplification. Since $A$ doesn't know $t_B$, members may end up with multiple shares. This is fine. I'm also assuming there's a max value $t_B$ can take that $A$ can share to, so that at the end of all the decryptions, there's no group of fewer than $t_B$ members that can reconstruct the secret.


texts: Is python a secure programming language for cryptography?

texts: I know Python is a powerful programming language but is it secure for cryptography? I mean is it possible to reverse engineer the program (written in python) and discover the algorithm of cryptography or other things?


texts: Relationship between Fibonacci LFSR and Galois LFSR

texts:
I'm studying about LFSR and have some troubles understanding LFSRs.

For Galois LFSR, it is clear that LFSR just multiplies $x$, the primitive element of $GF(2^n)$, so that it makes all the elements in $GF(2^n)$.

But for Fibonacci LFSR, it seems somewhat awkward.

In the answer at math.stackexchange, it says each register of Fibonacci LFSR is the dual basis of Galois LFSR, but can't we express it in the polynomial term?

And I also wonder whether the 'mirror' polynomial scheme, like $x^4+x^2+x^1+1$ vs $x^4+x^3+x^2+1=x^4(x^{-4}+x^{-2}+x^{-1}+1)$ can help to understand Fibonacci and Galois LFSR.


texts: How can I make my cipher show the avalanche effect?

texts:
I am a beginner in cryptography. I designed an password based encryption-decryption algorithm, which uses a random salt and a password to encrypt a message. I'm using SHA-512 for hashing, matrix operations for shuffling, bitwise XOR for mixing data and retrieving. The length of the salt and the ciphertext is 256 letters.

To my knowledge, the avalanche effect means that a slight change in any of the following:

cipher
password
salt

must change the output drastically.

In my implementation, if I change the salt or the cipher, I don't see any big changes in my output. However when there is a slight change in password, the output changes drastically.

So, my questions:

Is my understanding of the avalanche effect generally correct? If not, what should it be?
What can I do to best produce the avalanche effect in my (or any) cipher? should I reduce the salt length less and generate a smaller ciphertext to create an avalanche effect? If not, then how can I achieve this?


texts: Does larger key size mean larger data size in asymmetric encryption?

texts:
I'm new to cryptography. I know the larger the key size (like 128-bit vs 1024-bit) the harder the ciphertext is to crack, generally. But assuming everything else being equal, does a larger key size increase the data size compared to the original data in asymmetric encryption? I know AES doesn't increase the data size, but what about RSA?

I've been Googling my question, but I haven't found a straight answer. I just hope the answer is not "it depends", thus I added "assuming everything else being equal".


texts: Reversible Decryption in Symmetric Key Algorithms

texts:
I am currently learning the Internal Working of Symmetric Key Algorithms, like DES, AES, BlowFish, IDEA just to name a few.

These are all quite complex Encryption alogrithms, which requires a lot of confusion and diffusion of the Plain Text to produce the
corresponding Cipher Text.

But one thing that most of these (if not all) have in common is the fact that their decryption algorithms are sort of reverse of
the encryption algorithm used to encrypt them.

For Ex:-

  DES decryption requires the Key Portions to be revealed in reverse order (Ex. if K1, K2, K3....K16 were used for encryption, then
    for decryption the same encryption algorithm must be feeded keys in order K16, K15, K14...K1)

  IDEA decryption requires some ulteration in Key Generation, and the pattern of subkeys. And the decryption subkeys are
    actually the inverse of the encryption subkeys.

  BlowFish decryption process requires the reversal of P-array values

  AES decryption requries the reverse of encryption process (inv Sbox, inv CMatrix etc)

The question is, why are the encryption and decryption so much similar.

1) Are these algorithm's made while keeping their decryption process (Easy Reversibility without any extra algorithm/hardware) in mind?

2) Or is this a property that Symmetric Key Algorithms exhibit in general?


texts:
I'll keep this brief. I'm a maths teacher in the UK looking at a career change into cryptography, especially the mathematical side of it - I've studied analytic number theory recently and really enjoyed it. Unfortunately I have essentially 0 coding experience, so what would be a good place to start if I'd like to start looking at grad schemes soon? Many thanks.
(sorry, didn't know what tag to use so I put number theory as that's what I've been studying)


texts: Hamming Distance vs. Index of Coincidence

texts:
When analyzing a repeating-key xor cipher to find the key length, I've read about two key methods (assuming there aren't just repeating chunks of ciphertext for Kasiski's method), for some assumed key length $l$, checking the Hamming distance of nearby chunks of ciphertext of length $l$, and checking the IoC for columns of text when the text is split into $l$ columns.

When are Hamming distances more effective, and when is the IoC more effective? Is there any way to know based on the ciphertext which technique will be more helpful, or is this a "try them both and now it's more an art than a science" sort of thing?

See also: previous discussion of these methods.


texts: I don't care about replay attacks. What should I do with the nonce in nacl?

texts: My system forwards encrypted and/or signed messages on a gossip network. Replay is part of the design. What should I do with the nonce? I'm tempted to just set it to the same number always. Is this a bad idea?


texts: Decryption of Alternating Step Generator

texts:
I have programmed an alternating step generator in the following way:

I have three LFSR. LFSR_1 is being clocked in every step.
Every LFSR has an initialization vector.
And we have a text to encrypt.

If the output of LFSR_1 is 1 :

LFSR_2 is being clocked and calculates its new output. LSFR_3 is not being clocked.
We build the sum of the output of LFSR_2 and LFSR_3 ("xor")-> sum23
Then the sum23 is XORed with the 1. bit of the plaintext we have to encrypt and this is the first bit of cipher.

If the output of LFSR_1 is 0:

LFSR_2 is not being clocked but stays the same.
LFSR_3 is being clocked and calculates its output.
We build the sum of the output of LFSR_2 and LFSR_3 ("xor")-> sum23
Then the sum23 is XORed with the next bit of the plaintext we have to encrypt and this is the next bit for the cipher...

My question is: I have to decrypt the cipher to the plaintext again.  But I don't know how to do that?


texts: primitive root of a very big prime number (Elgamal DS)

texts:
For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime number (1024) or (2048) bits length.

My question is: how does the encrypter solve this problem?

I presume a loop to check all the possibilities is an option.


texts:
Assume we have a pseudorandom function: PRF(.)

We want the following property holds with a high probability:

$\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$

where $k_1$ and $k_2$ are two random keys picked independently.

Question 1: What is the pseudorandom function with the above property called in the literature?

Question 2: Is there any paper using the above pseudorandom function?


texts:
In Lyu12, Lemma 3.6 is as follows.

Lemma 3.6     For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the  $SIS_{q, n, m, d}$ decsion problem to the $SIS_{q, n, m, (2\alpha+1)d+\alpha}$ decision problem.

Proof. To prove the lemma, we will show a transformation that maps the  $SIS_{q, n, m, d}$ distribution to the $SIS_{q, n, m, (2\alpha+1)d+\alpha}$ distribution, and maps the uniform distribution over $\mathbb{Z}^{n\times m}_{q}\times \mathbb{Z}^{n}_{q}$ to itself. Given $(A, t)$, create a random vector $r \stackrel{\$}{\leftarrow} \{-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, \alpha \}^{m}$ and output $(A, (2\alpha+1)t+Ar)$. First observe that because $2\alpha+1$ is relatively prime to $q$, our transformation maps the uniform distribution to itself. And if $(A, t)$ canme form the  $SIS_{q, n, m, d}$ distribution, then  $(2\alpha+1)t+Ar=A((2\alpha+1)S+r)$, and since $s$ was chosen from the uniformly at random from $\{-d, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, d \}^{m}$, it's not hard to see that $(2\alpha+1)S+r)$ is uniformly random in $\{-(2\alpha+1)d-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, (2\alpha+1)d+\alpha \}^{m}$.

I don't know the role of $gcd(2\alpha+1, q)=1$ in  the proof. Why not create an problem $SIS_{q, n, m, d+\alpha}$ and reduces  $SIS_{q, n, m, d}$ decsion problem to the $SIS_{q, n, m, d+\alpha}$ decision problem?


texts:
I came up with this question while unit testing a function that includes an HMAC. What is the expected behavior of an HMAC with a well-defined key and a set of data with no elements in it? Is there such a concept as a "null HMAC"?

For example,

byte[] key = RNG.RandomData(32);
byte[] data = { };
byte[] hmac_result = HMAC.HMAC(key, data)

Ignoring the specific language or library I used, is hmac_result well-defined (based on the value of the key or specific HMAC algorithm used), or should the function return an exception?

I'm looking for an answer backed in theory, as I could believe different HMAC implementations could choose to raise an exception on questionable input data.

If the answer depends on the hash function used, what  factors would lead to the result being well-defined or not?


texts: Where can I find examples of ECC implemented in VHDL?

texts:
I am looking into implementing ECDSA signature and ECDH key agreement in a Xilinx FPGA.

All the examples I have found of VHDL implementations skip over how to construct the low level ECC primitives (e.g. point multiplication, MOD P in prime fields, and specially Inversion.

Can anyone point me to documentation or a simple implementation of a small field size like F23?


texts: Number of false keys in exhaustive key search for block ciphers

texts:
I'm doing a self study through Understanding Cryptography by Christof Paar and I have a question about Theorem 5.2.1 in the book:

Given a block cipher with a key length of $k$ bits and block size of $n$ bits as well as $t$ plaintext-ciphertext pairs $(x_1, y_1)\cdots(x_t,y_t)$, the expected number of false keys which encrypt all plaintexts to the corresponding ciphertexts is $2^{k-tn}$.

My understanding of the "proof" is that you treat the brute force attack process as picking $2^k$ permutations independently and uniformly at random.  The probability that a random permutation encodes $x_1 \rightarrow y_1$ is $1/2^n$ as there are $2^n$ choices for the ciphertext and each are equally likely.  So the expected number times that we encounter $x_1\rightarrow y_1$ is $2^k/2^n$.  Now, the probability of a random permutation mapping both $(x_1,y_1)$ and $(x_2,y_2)$ is $\frac{1}{2^n}\frac{1}{2^n-1} > 2^{-2n}$ so for $t$ pairs, it's $\frac{1}{2^n}\frac{1}{2^n-1}\cdots\frac{1}{2^n-(t-1)}>2^{-tn}$ so the expected number of false keys should be $>2^{k-tn}$.  I.e., this is a lower bound on the expectation rather than the expectation itself.  Though it seems that in general $2^n\gg 1$ so it's we should be able to write $\approx$ instead.  To get the number of "false keys", we would subtract 1 from this number (since this count includes the "true key" as well).
The text then goes on and use this formula for $k=80, n=64, t=2$ and interprets the result as

the likelihood of a false key $k_f$ that performs both encryptions $e_{k_f}(x_1)=y_1$ and $e_{k_f}(x_2)=y_2$ is $2^{80-2\cdot 64}=2^{-48}$.

Questions:

Did I miss something in the analysis or should this really be an equality instead of an approximation (or lower bound)?
How/why are we interpreting the expected number as a likelihood?
There something odd about the random permutations approach.  The argument seems quite loose. There are $2^n!$ permutations and I imagine we usually have $2^k \ll 2^n!$ so we're only enumerating a very small part of the set of all  permutations when doing the brute force key search.  It's really not equivalent to choosing permutations uniformly at random.... Is there more intuition that someone can help provide?  Maybe I'm missing something that's well known in cryptography?  Is there another way to do this analysis that's more precise?  Any pointers would be greatly appreciated.


texts: How to generate Multiple Encryption Keys for use in RSA polymorphic multiplication

texts:
I am a long time scroller, first time poster in the crypto stack. I've recently been finding myself leaving the realm of mainstream/standard crypto (imo that consists of symmetric/asymmetric encryption, some ciphers and one way hash functions ect). I am currently faced with a problem regarding using the RSA algorithm through multiparty computation. I am using RSA to conduct multiplicative homomorphic encryption using multiple keys. I am able to provably generate the encryption keys along with the final cipher text after multiplying all the values together. However I am not able to generate the correct decryption keys.
Process for encryption using RSA MPC
\begin{align}
C_1 &= a^{e_1} \pmod n \\
C_2 &= a^{e_2} \pmod n  \\
C_{final}&= C_1 \cdot C_2 = a^{e} \pmod n,\ \text{where} \ e=e_1 + e_2
\end{align}
The issue is that this only I can only really do this with a single encryption key (so if you consider $e_1=e_2$), whereas I would like to use multiple encryption keys ($e = e_1 + e_2$ or something equivalent), encrypt a value do some operation on that encrypted value then be able to decrypt it and receive some meaningful output.
Can someone help me with the problem of where to find details on using multiple encryption keys in RSA and working with the encrypted values directly ?
Research I based my working from: https://www.researchgate.net/publication/335743662_Enhanced_Homomorphic_Encryption_technique_using_RSA_ALGORITHM_with_multiple_keys


texts: request for data to test deterministic ecdsa signature algorithm for secp256k1

texts:
I’m implementing the RFC 6979 procedure to compute a message signature. I want to test my program on the secp256k1 elliptic curve. Note the “k” in secp256k1, i.e. the Koblitz curve.

If you have the reliable implementation of RFC 6979 on your machine, I would like you to post data that I could use to test my code.

The data should look like this:

The private key in hexadecimal form that you use.
The message in plain text or in hexadecimal form that you use before it’s hashed. I will use SHA256 to obtain the hash of the message.
The value of “k” in hexadecimal form that your software produces.
The value of “r” in hexadecimal form that your software produces.
The value of “s” in hexadecimal form that your software produces.
Optionally, the complete signature in hexadecimal form that your software produces.


texts: What is meant by encrypting/decrypting a known plaintext/ciphertext with every possible key in meet-in-the-middle?

texts:
I am working on the Meet-in-the-middle attack on 2DES and I have got some questions I am not sure about. I read several websites/articles about it so I have got an idea of what it is and how it works. However, I do not fully understand what is meant by every possible key.

Let me give an example:

I have a known plaintext, which I encrypt with 2DES - My key only has 20 effective bits of the 64 bits. So, the 20 bits are set as the high order and the rest is padded with zeros (have skipped over all parity bits). This gives me a ciphertext, which is encrypted twice with two different keys. So, when I want to perform a MITM attack on it, I have to encrypt the known plaintext with every possible key (= 2^20) and store the results i.e. the intermediate cipher and the key used in a, let's say, a HashMap where the input is  - The Hash key is not an integer.

Next, I have to decrypt the known ciphertext with every possible key and find a match between the decrypted cipher text and one of the encrypted plaintexts in the HashMap.

What confuses me here is what is meant by "every possible key"? Are 2^20 keys generated with random 20 bits (in my case)? If so, this would result in collisions.


texts: How can I implement decryption for NTRU homomorphic encryption scheme?

texts:
I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic encryption scheme suitable for a multikey context.
Multikey means each party encrypts its input with its unique key, the server computes homomorphically some evaluations and in the final stage, parties run an MPC protocol for decryption.

I have not understood this phase yet and I can imagine two ways to do it :

compute the NTRU decryption as a function by a MPC protocol
prove that NTRU homomorphic encryption scheme can be used to build a threshold homomorphic encryption scheme following the template from Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE by Asharov et al.,
   namely, replacing the BGV scheme with the NTRU homomorphic encryption scheme.

What is the correct implementation ?


texts:
I have a base64 'cipher' text. I know that in clear text is a hidden XML document (I know nothing about its structure), but the base64 alphabet was somehow shuffled. Is there any smart way, how to detect the modified alphabet better than checking all 64! permutations? I can slightly reduce the number of permutations by using the knowledge that XML document starts (without doctype, just root element) with opening tag (character '<') and ends with '>'. But there are still 62! permutations which are still not computable.

I have also tried to infer some other characters, but as the tags may be arbitrarily long and the content may be any character, I don't see much space for frequency analysis.


texts:
Given both Alice and Bob must exchange IP addresses to perform such an operation, what is the most secure way Alice and Bob can exchange public keys between two mobile devices without having to rely on a third-party server or hosted database of a website?

And yes, while i understand the key is PUBLIC, my goal is to exchange keys WITHOUT the key being stored on a third-party server or hosted database, accessible to the site administrator.


texts: How can two UProve token holders prove to a 3rd party that they aren't the same user?

texts:
Suppose I have two users who are issued two different UProve IDs.  The Issuer has guaranteed that one UProve token bearer will never have more than one UProve token ID.

How can I use UProve to guarantee that two users are "different" without disclosing their actual private ID?

Here is a scenario:  An online voting system wants to use UProve to anonymously collect votes.  They decide to trust an Issuer who has full knowledge of the end user, but the relying pary has to accept the fact that they will know nothing about the end user at all.

The polling station (relying party) only needs to know that the same UProve ID wasn't used to cast a second vote.  The only UProve scenario I know of that would work here is proving the user's SSN (or similar fixed ID).

In this case I don't want to disclose anything.

Is this possible?


texts: Privacy of vote from tallying authority in El Gamal Voting Schemes

texts:
I've been reading this paper about ElGamal encryptions and its application in electronic voting:

http://www.win.tue.nl/~berry/papers/euro97.pdf

Section 2.3 talks about using Shamir secret sharing so that t-out-of-n authorities need to combine to decrypt an ElGamal ciphertext. This makes sense so that after multiplying the voters' individual commitments, authorities can combine to reveal the sum of the votes.

My question is, if this is the case, can the authorities not take advantage of this to decrypt individual voters' commitments since the commitments still use the same $g$ and $h$ values after all? Where does the security of the vote from the authority come from.

Section 3 talks about creating commitments using random values $b \in \{-1, 1\}$ and then posting another value $e \in \{-1, 1\}$ such that vote $= b \cdot e$, which I think might be where the security comes from, but does not expand further on this.

Any help is appreciated!


texts: Can I use signature(hash(message)) instead of signature(message)?

texts:
Background:

We use the TweetNaCl crypto library by Bernstein (tweetnacl.cr.yp.to) et al and we would like to stick to it. However, we have the need to sign large messages and the library does not explicitely support signing something that does not fit in a buffer of bytes. However, the 25 functions of TweetNaCl include the ability to hash (SHA-512) a message in pieces without the need to buffer for the whole message.

We consider:

So, we consider using s2 instead of s1 as defined below.

s1 = Ed25519Signature(message)
s2 = Ed25519Signature(Sha512(message))

The Ed25519Signature is computed with the TweetNaCl function:
"sm = crypto_sign(m,sk);"

Can we do this? Is s2 as secure as s1?

Edit 1: note that the "Ed25519Signature" function above is "crypto_sign" from TweetNaCl. It does hashing internally. So, the signature is computed by hashing already. The s2 approach hashes the message twice while the s1 approach does the hashing once.


texts: Hashes or ciphers with all rounds executed in parallel?

texts:
Pretty much every cipher or hash I've seen has multiple rounds the are designed to be run serially one after the other. Has anyone ever designed a fully parallel cipher or hash? This would be one where all rounds are executed in parallel and then the results are combined in some way such as addition or XOR.
It's mostly a theoretical question. It just occurred to me that I've never seen nor heard of such a thing.
It would be interesting from a performance perspective since you could use wide SIMD instructions to compute many rounds at once. It would also be easier to implement in hardware to run in one clock cycle.


texts: Why is MixColumns omitted from the last round of AES?

texts:
All rounds of AES (and Rijndael) have a MixColumns step, save the last round which omits it.  DES has a similar feature where the last round differs slightly.  The rationale, if I recall correctly, was to "make the cipher appear similar in reverse as it does in the forward direction."

Why does this make AES$^{-1}$ look similar to AES?  And how does this help in implementing the block cipher?


texts: Is there a way to do anonymous encryption to a recipient?

texts: Is there a way to do anonymous encryption to a recipient's Public key, where the only way to open a message would be to decrypt with your own private key + passphrase?


texts: In BBC Sherlock's The Blind Banker, what type of cryptographic function is used by the Black Lotus?

texts:
In BBC’s Sherlock, Season 1, Episode 2 “The Blind Banker”, the Black Lotus crime syndicate uses ancient Chinese number characters to refer to pages and words in a commonly known book (which was currently the A-Z London Guide).

What class of cryptographic functions would this most closely fall under? Is it symmetric/private key encryption? Or asymmetric/public key encryption? Or something else?

My understanding is that the key is the common book, and the Chinese characters are the ciphertext of the original words. Hence this would make it symmetric encryption? But at the same time, the book is publicly accessible so it's not strictly a secret/private key.


texts: Just a super basic question - Does the key create the algorithm?

texts:
I don't understand how the key gives you the algorithm, in other words I am having trouble understanding how the key works in symmetric encryption. My book says:

  "Symmetric encryption transforms plaintext into ciphertext using a secret key and an encryption algorithm"

So what does the secret key do, is it like  a password to give you access to the actual encryption? Also my book says:

  "Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key"

It says "generated with the secret key", so the key creates the algorithm?


texts: Why is the signature field in X.509 a BIT STRING, despite there being ASN.1 (DER) data inside?

texts:
As can be seen from the following ASN.1 definition of an X.509 certificate, the Signature field is a BIT STRING.

Certificate ::= SEQUENCE {
    tbsCertificate      TBSCertificate ({ x509_note_tbs_certificate }),
    signatureAlgorithm  AlgorithmIdentifier,
    signature       BIT STRING ({ x509_note_signature })
}

However, at least for the rsaEncryption algorithm, there's ASN.1 DER data inside (representing the signature).

So, why is it a BIT STRING?
Wouldn't something like SEQUENCE or just OCTET STRING work better?


texts: Are AES-256's related-key weaknesses exploitable if it is used to build a hash?

texts:
Assume it is made a hash based on AES-256 encryption (perhaps because this is hardware-accelerated, but no standard hash is); and it is used the Merkle–Damgård structure, that is padding of the message into $n$ padded message blocks $M_i$ (appending to the message a 1, a minimal number of 0, and the 64-bit message length in bits), and a compression function per the construction of either

Davies-Meyer for a 128-bit hash with 256-bit blocks $M_i$, that is

$H_0$ is set to a 128-bit nothing-up-my-sleeves constant;
for $i$ from $0$ to $n-1$:
$\text{ }H_{i+1}=\text{AES-256}_{M_i}(H_i)\oplus H_i$
result is $H_n$;

Hirose (FSE 2006) for a 256-bit hash with 128-bit blocks $M_i$, that is

$G_0$ and $H_0$ are set to a 128-bit nothing-up-my-sleeves constants;
for $i$ from $0$ to $n-1$ (with $C$ a non-zero nothing-up-my-sleeves 128-bit constant)
$\text{ }\begin{align*}
G_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i)\oplus G_i\\
H_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i\oplus C)\oplus(G_i\oplus C)
\end{align*}$
result is $G_n||H_n$.

Notice that in both of these constructions, the message that the adversary can manipulate is entered in the key input of the cipher, making related-key attacks a concern.

Question: In these contexts, are any known or foreseeable AES-256 related-key weaknesses exploitable or seriously threatening?

If yes, do we have other hash constructs where AES (any size) related-key weaknesses would be less of a concern?

Note: For the 128-bit hash we expect an effort comparable to $2^{64}$ encryptions to exhibit a collision (that can be efficiently distributed, see Parallel Collision Search with Cryptanalytic Applications); and $\min(2^{128},2^{129}/n+2^{65})$ encryptions to exhibit a (second) preimage (by a generic attack on Merkle–Damgård hashes attributed to R. D. Dean in his 1999 thesis (section 5.3.1), better exposed and refined by J. Kelsey and B. Schneier in Second Preimages on n-bit Hash Functions for Much Less than 2n Work).
For the 256-bit hash we expect an effort comparable to at least $2^{128}$ encryptions to exhibit a collision, and much more to exhibit a preimage.


texts: Distribution of safe primes generated using different techniques

texts: Is there any difference in the distribution of safe primes generated by creating prime $q$ and testing $2q+1$ for primality, compared to generating a larger prime $p$ and testing $(p-1)/2$ instead? The former is what is used in practice for efficiency. For the purposes of this question, I am assuming primality is determined by creating an odd integer, subjecting it to a sufficient number of Miller-Rabin tests, and incrementing it by two if it is composite before testing it again.


texts: Can I get an explanation of HDCP's key exchange protocol?

texts:
I'm talking about HDCP v1.x. The specification is a too dense for me and easy-to-understand information about it on the net is scarce.

What I've gathered is:

that there is a master key that is a 40-by-40 matrix of 56-bit values.
each device that is part of the HDCP ecosystem has a unique array of 40 secret keys generated such that a shared value can be calculated from two different arrays and selection vectors.

How does the key exchange work and why does it work? How is the master key related to each device's unique array of secret keys?


texts: A quick question. I want to use the last character of a SHA256 hash (blockhash of a bitcoin block) as my random source. Is 100 /16(amount of different chars) = 6.25% true for all characters or are some characters more likely to be the last char of a hash.


texts: Caculating Correlation for CPA attack on AES

texts:
I am having some trouble understanding how to calculate the correlation coefficient for CPA attack on AES.

In the article Study of Deep Learning Techniques for Side-Channel Analysis and Introduction to ASCAD Database, they actually keep 700 measurements for the computation of 1 SBox (page 11), in step 7 of the algorithm (page 12).

But when we want to calculate the hamming distance between the input and output of that computation for a guessed subkey, we will get a single value representing the distance. So how will we calculate the coefficient between the measurements and the hamming distance? Since we have 700 measurements for the same instruction, but only one hamming distance.


texts: Strength of $H(k\|H(m))$ as a MAC algorithm

texts: What is the strength of $H(k \| H(m))$ compared to HMAC? Compared to $H(m \| k)$? What is the strength in bits of a given key/output size?


texts: Google today announced they are sunsetting SHA-1. Its fine by me. But that made me realize I am not keeping up with the research on SHA-1. The Wikipedia page only says Stevens' attack is the most efficient but its also on a reduced round SHA-1 - not the SHA-1 with the full rounds. So is there no theoretical attack on SHA-1 or is the one I referred to above enough for it to be considered vulnerable? Are there others?


texts: Standard for Second Preimage Resistant Hash Functions

texts:
Some PQC schemes don't require collision resistance for their hash functions, thus using a hash function faster than the SHA series that only considers the pre-image and secondary pre-image resistance would speed up these schemes.
Is there such a standard for hash functions that 1st and 2nd preimage resistant but not necessarily collision resistant?


texts:
For Vigenere cipher, I understand

Find period first (say we have p = 6)
Find highest frequency of letter in each group (from 1 to 6) and assume it is "e" in plaintext

What if we have more than one letter with same frequency. For example, "j" and "y" having same frequency in p1 group. Which one should we consider when finding a key?


texts: Unilateral authentication with implicit key authentication

texts:
Is it possible to design a cryptography protocol with achieving unilateral authentication of one party A by party B using implicit key authentication?
Key authentication is the property whereby one party is assured that no other party aside from a specifically identified second party (and possibly additional identified trusted parties) may gain access to a particular secret key. [Handbook of Applied Cryptography, 12.6 Definition]


texts: Is there an interactive proof protocol for proving that a preimage in a map $g: Z_{q}^{n} → G_{T}$ is mapped to a given public value, say y?

texts:
There already exist interactive proof protocols with logarithmic communication for proving that a secret multi-exponent $x ∈ Z^{n}_{q}$ for a public multi-exponentiation $P = \textbf{g}^{\textbf{x}} ∈ G$ is mapped to a given public value y under an arbitrary but given group homomorphism $f : Z_{q}^{n} → G_{T}$, where $\textbf{x}  ∈ Z_{q}^{n}$ and $\textbf{g} ∈ G^n$ . For example, https://eprint.iacr.org/2020/753.pdf.
I was wondering if the same thing was possible where the map is not a homomorphism, but we allow for linear communication in group elements, and we do not require that x be in the form of a secret multi-exponent (Although it wouldn't hurt).


texts: Do I need to use HMAC in this crypto wallet backup application?

texts:
I'm building an application for securely backing up cryptocurrency private keys or 12-word backup phrases that crypto wallets use as a seed to generate private keys. For the purpose of this question, if you're unfamiliar with cryptocurrency, you just need to know that whoever knows your private key can spend your money.

This is the backup process:

The user encrypts his plaintext with a password (I'm using scrypt and AES256)
The ciphertext is base64-encoded, and both the ciphertext and some header data are encoded as a single QR code -- this is the user's backup
The user prints several copies of the QR for storage
If the user's computer crashes and he needs to restore his backup, he can scan the QR code and provide the password to decrypt the message and retrieve his private key(s)

The QR code contains the scrypt parameters, salt, initialization vector, and the ciphertext.

My question is: Do I need to add an HMAC signature to the contents of the backup? If possible, I'd like to leave it out, since it significantly increases the complexity of the resulting QR code, and complex/large QR codes are more difficult for devices to scan.

I'm thinking I don't need an HMAC signature because, if the ciphertext is altered in any way by a malicious party, the resulting altered plaintext will be useless to the user - he won't be able to recover his cryptocurrency. Altering the ciphertext would produce the same results as simply destroying the user's backups (a signature can't protect against that). A length extension attack would also be pointless in this context.

The fact that an altered backup is useless seems like a built-in integrity check, making a signature redundant. Is this conclusion correct, or do I need to add a signature?


texts:
Is it possible to do the following?

Input would be to generate a new AES key, encrypt the private data with that key, encrypt the AES key with the FHE key, and send the FHE-encrypted AES key along with the AES encrypted data to the compute node.


texts:
I would like to know if I am understanding this correctly.
Zero-knowledge proofs need a prover, verifier and witness.

So if we have a blockchain where person A pays person B 100 dollars.
In blockchain, is person A the prover? It proves to the other nodes (the verifiers) that person A has 100 dollars. A witness applies a hash function to the verifier..

Am I understanding this wrong?


texts: How can I find the multiplicative inverse in the first transformation of the SubBytes() transformation in AES?

texts:
In FIPS-197 §5.1.1, it says the first transformation in the SubBytes() transformation is:

  Take the multiplicative inverse in the finite field $\text{GF}(2^8)$ described in Sec. 4.2; the element $\{00\}$ is mapped to itself.

Looking at Sec. 4.2, it says that for a given non-zero polynomial $b(x)$ you can find the inverse $b(x)^{-1}$ by using the extended Euclidean algorithm. My question is basically: how do you do this?

I've looked at a ton of examples, Wikipedia has one in $\text{GF}(2^8)$, but I still just don't understand.

Let $b(x) = x^6+x^4+x+1$, Rijndael has $m(x)=x^8+x^4+x^3+x+1$.

From the relation: $$b(x)a(x)+m(x)c(x)=1 \iff b^{-1}(x) \equiv a(x)\pmod{m(x)}$$ I can't figure out what $a(x)$ and $c(x)$ are.

The higher level explanations maybe assume you know some things, and the basic explanations

only use simple integers with Euclid's algorithm, so it's a frustrating place for a beginner.


texts: Public key cryptography instead of passwords for web authentication

texts:
The usual way for a user to authenticate themselves to a website at the application layer is with a shared secret - the user's password. If a user is connecting to a bank, they give the bank their password, and the bank stores the password, hopefully not in plaintext, but as a salted hash run through a slow KDF.

There are some weaknesses to this scheme, for example the fact that users tend to reuse passwords across websites, and that many server operators do not take the appropriate precautions when storing their users' passwords. Even if a user randomly generates strong passwords for each website, the server could still lose the password, so the user must trust the server operator to safely store the password.

If a public key scheme was used, similar to SSH key authentication, the user would not have to trust the server. The server could store the user's public key, which compromises nothing if stolen. If the user's private key is stolen, they can still revoke the key, preventing the thief from using it.

SSH supports this kind of authentication.
Are there any existing systems that do authentication to websites, as opposed to SSH servers, like this?

Basically, are there any systems that replace user passwords with signatures from the user's private key?


texts: Authenticating to wireless with EAP-TLS in separate forests with the same trusted root CA

texts:
I'm looking at a scenario of having a standalone offline root CA sign a subordinate CA in two separate active directory forests on different campuses.

If I then set up EAP-TLS on each site, will I be able to authenticate with EAP-TLS on either campus if the client has a computer certificate from either subordinate CA?

Assume the client trusts the root CA.


texts: Is this an example of a zero knowlege proof?

texts:
My Math Structures professor mentioned the strange concept of a zero knowledge proof to me after class one day, and I decided to do some reading about it. After reading the relatively famous "How to Explain Zero Knowlege Protocols to Your Children", and the Wikipedia page on zero knowledge proofs, I wanted to see if I could construct a protocol for a proof myself. After a bit of thinking, I believe the one that follows completes a zero knowledge proof.

Let Peggy be the prover and Victor be the verifier
Peggy is trying to prove that she knows $(p,q)$

Peggy picks two random large primes $p$ and $q$
Peggy gives Victor $L=pq$
Peggy picks two random large primes $r$ and $s$
Peggy gives Victor $C=rs$
Victor randomly either asks Peggy for either $r$ or $pr$
Victor verifies Peggy's response $m$:

If Victor asked for $r$, he checks that $m\mid C$ and that $C/m$ is prime
If Victor asked for $pr$, he checks that $m\ne C$ and $m\neq L$ and that $m\mid LC$

steps 3 through 6 can be repeated to reduce the chance Peggy could have guessed what Victor was going to ask for.

I think this protocol works because factoring large pseudoprimes is infeasible, and Peggy can fake responses if she knows what Victor is going to ask for.

If Peggy knows Victor will ask for $r$, she just does the protocol as normal (sending $r$ when asked). If she knows Victor will ask for $pr$, she sends $C^\prime=rsn$ initially (for some $n$ and prime $r,s$), and then sends $rn$ when Victor asks for $pr$.

Now I would like if someone more experienced than me could let me know: does my protocol successfully perform a zero knowledge proof? If not, do I appear to have some simply correctable misunderstanding, or did I maybe miss a couple details?


texts: Public key encryption algorithm for short messages

texts:
I need to encrypt a high number of short messages (30-200 bytes). The problem with usual algorithms, such as RSA, is that the size of the encrypted message tends to increase a lot, compared to symmetric encryption algorithms.

Ideally, this cryptosystem shoud accomplish:

Asymmetric
Size of the encrypted message must be at most 25% longer than the original
Should be fast encryption and decryption
It's not a problem if, after some work, some messages are decrypted
But private key must not be found so easily
It would ve good if it's a known algorithm with solid implementations in most common languages

The only solution I found until now is using RSA with short keys (64 bits), but I wonder what a better approach could be.


texts: Why is a common reference string needed in zero knowledge proofs?

texts: Can we have a non-trivial language without a CRS? Why?


texts: Are there any SSL cipher suites that will not be affected by the post-quantum world?


texts: Block Cipher vs Stream Cipher in Web Application

texts:
I'm doing research about "Cryptographic attack methods in Web Application" so I have some questions to ask you guys:

Block Cipher vs Stream Cipher, which is more common used in Web Application?
How and Where is Stream Cipher implemented in Web Application?

Hope to get your response soon :)


texts: Key derivation of public key without knowledge of private key

texts:
I'm looking for a convenient way to share a set of public keys across multiple services, while preserving privacy by preventing these services from tying the identity of these public key sets together across services.

E.g. If I share my public key set with both Service 1 and Service 2, Service 1 and Service 2 should not be able to work together to discover that I have an account on both services.

Note that I don't want to simply generate a new set of key pairs for each service, as the private keys are distributed across multiple devices for security reasons (to avoid a single point of failure), and generating a new key pair on each of these devices every time I want to set up authentication for a new service would be inconvenient for the user.

While considering the best way to satisfy these requirements, I believe I've reduced the problem to the following:

  Given a public key Kpub and some other bit of information x, I want to derive a public key K'pub such that the holder of Kpriv, and only that keyholder, given x, can find K'priv, and such that it is hard to find Kpub given K'pub and x.

So basically, it seems I want a key derivation function that can derive a public key, but which can't derive the corresponding private key without knowing some additional, secret information.

Is this possible? Is there any existing solution which satisfies the above requirements? Or am I breaking new ground here?


texts: For the scrypt HMAC storage format, why run the input of the hash and the hash itself into the HMAC

texts:
Generally if the body is hashed, why provide the body and the hash as input into the HMAC.  Instead wouldn't the same security be achieved by hashing the body and providing only the hash as input into the HMAC?

I looked at the documentation here. I also looked at the answer here which provides detailed description of which byte is used for which algorithm.

These two documentations state that when computing the HMAC bytes 0 to 63 are used as input. Also, when computing the SHA-256 HASH bytes 0 to 47 are used as input.

Since any change in bytes 0 to 47 would change bytes 48 to 63.  Why bother providing bytes 0 to 47 as input into the HMAC.  Would the security be the same if the HMAC used bytes 48 to 63 as input?


texts: Struggling to understand Perfect Forward Secrecy

texts:
From the definition on Wikipedia:

  In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if the private key of the server is compromised.

So, if I am understanding this right, a protocol establishes PFS if the leak of the master key does not enable a calculation of already-used session keys.

But I read a question here that PFS can be achieved by deriving session keys with a hash of an old session key. But if I were to know the master key (the pre-shared key?), I could easily calculate all session keys or am I misunderstanding something?


texts:
I know the public modulus is the product of two primes. For key with length L, the public modulus N should be such 2^(L-1) <= N < 2^L.

However this implies that the most significant bit will be always 1. Doesn't this reduce the search space for the primes P and Q by half?

Shouldn't N be between 2^(L-2) and 2^L ?


texts: How can an adversary request decryption of an unused sector?

texts:
The Wikipedia article on Disk Encryption Theory mentions this

  a powerful adversary can modify an unused sector on the disk and then request its decryption.

I understand that an adversary is capable of modifying an unused sector, but can anyone explain how they would be able to request its decryption?


texts: Have affine ciphers actually been used in practice?

texts:
I have been been studying some basic ciphers, and learnt about the affine cipher where the encryption function is given by $ax+b \pmod{26}$ for an alphabet with 26 characters. This is a very insecure cipher, so if it was used it must have been a long time ago. I am aware that the Caesar cipher and the Atbash cipher are special cases of the affine cipher (with $a=1$ and $a=b=25$, respectively). However, when these two ciphers were used, the encryption was not performed mathematically using the affine function, but with a shifted alphabet.

So, my question is: Has the affine cipher ever been used in practice (with $a\ne1$ and $a\ne b\ne25$), where the encryption was performed mathematically using the affine function?


texts:
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about AES algorithm the authors say that in the last round of the encryption algorithm the MixColumn layer isn't applied, since it only slows down the decryption algorithm. But this doesn't decrease the security of the algorithm ?

I cite:

  The preceding shows why the MixColumn is omitted in the last
  round of the encryption algorithm.Suppose it had been left in.[...]This means the decryption would have an unnecessary "Inverted Mix Column" at the beginning of the decryption algorithm, and this
  would have the effect of slowing down the algorithm.

ps: it's also said that the elements of the Inverted MixColum matrix are more complex in respect of the elements of the MixColum matrix (i cite "and this is enough to make decryption take
around 30% longer than encryption for certain types of processors"). Also this isn't explained. Do you know why ?


texts: Dilithium signature scheme - Public key derivation

texts:
Good day!

I am very new to Cryptography but I want to make sure I understand the concept of the scheme correctly before using it to our system. So I was looking at post quantum signature schemes, and I came across Dilithium(https://github.com/pq-crystals/dilithium), and our system currently runs on Ed25519 which based on my question can easily take a secret key and generate a deterministic public key from it.

So my question is, can Dilithium also be useable on this type of implementation, like what Elliptic Curve stuff can do? Because based on the white paper I have read in Dilithium, I just need the random 256 bit seed, and I can create the pk and sk, but I cannot take an sk and derive a pk from it. I can however get the 256 random key and generate a key from it, but it just makes the same key as the first key generation.

Let me know if this makes sense.

Thank you.


texts: ECDSA where the group order is larger than the hash size?

texts:
According to wikipedia, when generating a signature for ECDSA, you do the following (among other things):

  Calculate $e=\operatorname{HASH}(m)$, where $\operatorname{HASH}$ is a cryptographic hash function, such as SHA-2.
  Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of the group order $n$.

$z$ is later used to calculate $s$.

Anyway, my question is...  what if $L_n$ is larger than the bit length of $e$?

For example, SHA256 has is 256 bits long. secp384r1, in contrast, has a bit length of 384 bits.


texts: is it unsafe to AES encrypt using multiple modes?

texts:
Example:
message = 'sup'

// encrypt
cipher = aesencrypt(aesencrypt(aesencrypt(message, 'CFB'), 'CTR'), 'OFB')

// decrypt
message = aesdecrypt(aesdecrypt(aesdecrypt(cipher, 'OFB'), 'CTR'), 'CFB')

if it's not a possible vulnerability, it'd just rather use all 3 than decide on one.


texts: How do I tack on "additional data" to libsodium's public-key authenticated encryption?

texts:
I note that libsodium provides AEAD when using symmetric cryptography.

And yet, under section 8 (Public-key cryptography) there are no public-key methods described which allow for additional data (AD) to be included.

Keeping in mind cryptographic best practices, is there an elegant way to essentially add the feature of additional data to a public key cryptographic AE method like crypto_aead_chacha20poly1305_encrypt?  That is, suppose that the libsodium building blocks remain as they are.  How do I add additional information sent in the clear that becomes part of the authenticated message?

And I'm curious if the absence of such a method now is for any particular reason.


texts: How to pass an arbitrary signature to a certificate

texts:
I am trying to sign certificate (X509) using secret sharing. That is shareholders combine their signatures to produce the final signature which will be in this case the signed certificate. However practically from my understanding only one entity can sign a certificate. Therefore I want to know:

which entities or data of the x509certificate are actually taken as input to the signing algorithm?
Ideally I want this data to be signed by the shareholders and then the final combination will be passed to the X509certificate as valid signature.
Is this possible?
How could it done?
If not are they other alternatives?


texts: How do I calculate the conditional probability of a Caesar cipher?

texts:
I have a frequency distribution of letters for the plaintext and the ciphertext.

I'm trying to determine the conditional probabilities to identify the plaintext/ciphertext pairings.

If I encrypt with Caesar cipher with the key of $3$, then $e$ will become $h$.

As I understand it, the conditional probability of $\Pr(M=e\mathbin|C=h)$ should be $1$ (or very close to it).

How do I calculate the conditional probability to prove that $\Pr(M=e\mathbin|C=h) = 1$?


texts: Why aren't Diffie Hellman public keys used for authentication?

texts:
So I have been reading about Diffie Hellman and specifically the MitM attacks that it is vulnerable to.

I am aware that these are solved currently in ssl for instance by using rsa signatures to authenticate dh public keys (as in the $g^a$ mod n bit) to prevent a middle man from compromising the connection.

I also am aware that the public key of the server that is used in the RSA authentication is provided by a CA which is how the browser knows it is valid.

I am also aware that DH as used in ssl is ECDH, but regardless I think my question still applies and I would be interested in an answer in reference to either ECDH or just normal DH.

What I don't understand however is why the certification authority (CA) can't simply give out the servers $g^a$ mod n (public DH key) instead of their public RSA key, as to avoid having to use RSA.

I know that one reason this is not used is because of forward secrecy which can only be gained with session based DH keys, but why has this never been implemented (from what I can tell, it hasn't) even though non forward secret RSA used to be used for this purpose?

Would having a persistent DH public key introduce a mathematical vulnerability or is there another reason why this hasn't been done?

Thanks you


texts:
I was wondering about an algorithm that would take a bitstring as an input, shuffle it and output it. You could use a deterministic RNG to select pairs of bits to swap, using the seed as some sort of password, handing it to people to let them reconstruct the shuffling process. Is this a good idea? Has anyone already thought of this? If not, are there any flaws I would have to bear in mind?
I'm a newbie to cryptography and I don't really know how to approach this.

Excuse my poor English grammar and thank you for your time!

EDIT: I forgot to specify that this is for learning purposes.


texts: Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution?

texts:
There is a version of LWE assumption as follow.

Assume that there is a positive number $n$, an integer $q = q(n) \geq 2$, an error distribution $\chi = \chi_{n}$, a vector $\mathrm{\mathbf{s}} \gets \mathbb{Z}_{q}^{n}$ and for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ A \gets \mathbb{Z}_{q}^{m \times n}, \mathrm{\mathbf{e}} \gets \chi^m,~  \mathrm{\mathbf{b}} \gets A \cdot \mathrm{\mathbf{s}} + \mathrm{\mathbf{e}}: \mathcal{A}(A, \mathrm{\mathbf{b}}) = s \right] \leq \mathrm{nelg}(n)$$

Q1: Why does it say $m = O(n \log q)$ in some schemes? I do not find some notes about the range of $m$. I think $m = \mathrm{poly}(n \log q)$ is OK.

Q2: Is there an adaptive version? Is it still hard to solve?

For example, Let oracle $\mathcal{O}_{\mathrm{\mathbf{s}}}$ satisfy that  $\mathcal{O}_{\mathrm{\mathbf{s}}}(\mathrm{\mathbf{a}}) = (\mathrm{\mathbf{a}},  \langle \mathrm{\mathbf{a}}, \mathrm{\mathbf{s}} \rangle + e)$, where $e \gets \chi$.
And for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ \mathcal{A}^{\mathcal{O}_{\mathrm{\mathbf{s}}}}(1^n) = s \right] \leq \mathrm{nelg}(n)$$
The algorithm $\mathcal{A}$ is allowed to ask the access of $\mathcal{O}_{\mathrm{\mathbf{s}}}$ for at most $m$ times.

Q3: If there are $l$ secret vectors and $S = [\mathrm{\mathbf{s}}_{1}, \mathrm{\mathbf{s}}_{2}, \ldots, \mathrm{\mathbf{s}}_{l}]$.
Is there a version of LWE with respect to some potentially non-uniform secret distribution? (e.g., $S$ belongs to the general linear group $GL_{n}(q)$ or the orthogonal group $S \in O_{n}(q)$)

It means that for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ \mathcal{A}^{
\mathcal{O}_{\mathrm{\mathbf{s}}_{1}},
\mathcal{O}_{\mathrm{\mathbf{s}}_{2}},
\ldots,
\mathcal{O}_{\mathrm{\mathbf{s}}_{l}}
} (1^{nl}) = S \right] \leq \mathrm{nelg}(nl)$$


texts: 7zip : Why does encrypting the same file with AES-256 not give the same output?

texts:
Using 7-zip 19.00, on Windows 10 1909, build 18363.592, I encrypted a text file with the contents "hello there" using AES-256 and the password "123". I did this two times, the exact same procedure, but as shown below, the output is different:

Why?


texts: Why does gnupg create 4 separate keys and what does sub and ssb mean?

texts:
When using gpg to create a single key, I get:

$  gpg --list-keys
-------------------------------
pub   2048R/0C0EA301 2018-01-01
uid       [ultimate]
sub   2048R/023A0509 2018-01-01

$ gpg --list-secret-keys
-------------------------------
sec   2048R/0C0EA301 2018-01-01
uid
ssb   2048R/023A0509 2018-01-01

When using bouncycastle to view the keys (in ~/.gnupg/pubring.gpg and ~/.gnupg/secring.gpg), I find that there are four keys created:

(#gpg.public[9AB238A08EF3EAB0A7D01E1284AB64C10C0EA301]
 #gpg.public[A841D2BA6635154081F3A5176DE7FF9B023A0509])

(#gpg.secret[9AB238A08EF3EAB0A7D01E1284AB64C10C0EA301]
 #gpg.secret[A841D2BA6635154081F3A5176DE7FF9B023A0509])

Why does gpg create four keys (public/private/sub/ssb) and what are they for?