Beginner question about secure communication with one user using DES I am currently learning about encryption and I was asked a question:

If a customer only had a DES system how could I secure messages as DES is not secure.

I was researching this and I came across a Hybrid crypto system, where a symmetric-key crypto system (DES) is used and a public-key crypto system is also used.

Would this be a viable option or do both parties need to use both systems?

Any help would be much appreciated.

Yeah, the question is something like "A customer wants to to secure their communications with <company> but the customer can only use a DES crypto system and does not have a shared DES key with <company>. How can they securely communicate without help from a third party?"

Well, the customer could call the company and arrange for a meeting with a representative.  After meeting the representative and verifying that they're really working for the company, the customer should hand the representative a note (or a thumb drive) with a randomly chosen DES key on it, saying "Here, use this to communicate securely with me."

(Actually, they should hand the representative two or three DES keys, and tell them to use triple DES, since a single DES key is too short to resist brute force attacks nowadays.)

If the customer and the company representative cannot physically meet, they could perhaps use e.g. the Diffie–Hellman key exchance protocol to obtain a shared secret value, and then each feed it to a key derivation function to turn it into a shared (triple) DES key.  However, Diffie–Hellman alone is not secure against active man-in-the-middle attacks — without some kind of a previously shared secret, there's no way for the customer and the company rep to know for sure that they've really swapped keys with each other, rather than each of them having exchanged keys with some third party who intercepted the original Diffie–Hellman exchange (and keeps intercepting their subsequent communications to decrypt, read, re-encrypt and relay any messages).

If the customer and the company do have some kind of a shared secret — say, a password — then it's possible for them to use a password-authenticated key exchange to "upgrade" the password to a shared (triple) DES key.  One fairly simple way would be for them to first do a normal anonymous D–H key exchange, but then concatenate the resulting shared secret value value with the password and feed it through a deliberately slow key derivation function to turn it into (triple) DES keys.  This ensures that, if a middle-man who doesn't know the password tries to intercept the key exchange, they will not be able to derive a matching DES key with either party.

(This simple protocol does have the weakness that the middle-man, having spoofed the D–H key exchange and intercepted at least one DES-encrypted message using the correctly derived key, now has enough information to mount an offline brute force attack against the password.  The security of this scheme is thus entirely dependent on the strength of the password and the slowness of the KDF.  At the very least, the customer and the company should minimize the attack surface by only using this protocol once, to exchange proper shared keys, and not repeating it later; better yet, they should use a more advanced PAKE protocol that uses an interactive zero-knowledge proof to convince the authenticating parties that they both have the same password and D–H key.)

Depending on the additional assumptions we may make, there can be other options as well.  For example, if the company has a private asymmetric encryption key, and the customer knows the corresponding public key, then the customer can simply generate a random (triple) DES key, encrypt it using the public key, and send the encrypted key to the company, knowing that, even if it's intercepted, only the correct recipient can decrypt it.

(Of course, this only lets the customer know that they're talking to the right company; it doesn't help the company know that the customer is really who they say they are, since the public key, being public, could presumably be used by anyone.  Also, it presumes that the customer somehow already knows that the public key they have really belongs to the company, and not to an attacker.)

Even if the company only has a private key for a digital signature algorithm, there are still ways it could be used to securely establish a shared (triple) DES key.  For example, the customer and company could start with a D–H key exchange, as above, and company could then sign their D–H secret value (preferably after hashing it, to make sure the signature leaks no information about the key) and send the signature (over the DES-encrypted channel) to the customer, who verifies it using the public half of the company's signing key.

In any case, my point is that this problem really has nothing to do with DES as such.  It's really a key-agreement problem, and the solution depends on what kind of existing shared information the customer and the company have (and what kinds of additional tools, besides DES, they many use).  If they really know nothing about each other that an attacker could not spoof, then the problem is strictly speaking unsolvable: if the customer has no way to tell if they're talking to the right company, an attacker can just intercept the customer's messages and reply to them, pretending to be the company.


Associative but NOT Commutative Reducing Function Construction with Existing Hash Function(s) Is it possible to construct a binary reducing function based on any existing cryptographic hash function satisfying the associative property but not the commutative property? So formally:

Using an existing hashing function
$h: \mathbb{B}^* \rightarrow \mathbb{B}^k $
to construct
$R: \mathbb{B}^* \times \mathbb{B}^* \rightarrow \mathbb{B}^{k'}$
so that

$R(R(a,b),c) = R(a,R(b,c))$, for all $a, b, c \in \mathbb{B}^*$ (associativity)
$R(a,b) \neq R(b,a)$, for some $a, b \in \mathbb{B}^*$ (non-commutativity)
$R$ is as secure as $h$ in sense of

pre-image resistance, applied to both arguments, and concatenated
second pre-image resistance, applied to both arguments, and concatenated
collision resistance, applied to both arguments, and concatenated
additionally, it should be as hard to find $a, b \in \mathbb{B}^*, a \neq b$ that $R(a,b) = R(b,a)$ as to find $a, b \in \mathbb{B}^*, a \neq b$ that $h(a)=h(b)$, except the case* where $b = R(a,a)$

where:

$\mathbb{B} = \{0, 1\}$, a bit
$k, k' \in \mathbb{Z}^+$, the output length of the hash and reducing functions

also, if needed, more than one base hashing function $h$ could be used.

Background

The purpose of this construction is to allow the calculation of a collective hash value of an ordered list that can be carried out with arbitrary combinations in any order of the reducing function. So the ultimate goal is to construct a function $H: (\mathbb{B}^*)^* \rightarrow \mathbb{B}^k$ that could be calculated by independent multiple steps.

*the reason to make an exception in the last property is that giving the application, it makes perfect sense that $H(\{a,a,a\})$ gives the same result regardless of how you calculate it (credit goes to poncho; refer to his answer).

This question is quite similar to Associative standard cryptographic hash function, but not exactly the same. This answer might be useful: https://crypto.stackexchange.com/a/17936/19959

I don't believe that any such function can meet the requirements of associativity, pre-image resistance and the 'hard to find commuting operands' simultaneously.

Here's why: suppose we have a preimage $a$; we first check if $H(a,a)=a$.  If it is, we found a preimage.

If $H(a,a) = b \ne a$, then we have $H(a,b) = H(a,H(a,a)) = H(H(a,a),a) = H(b,a)$ (because of associativity), and hence we found a commuting pair.


How can I create an RSA modulus for which no one knows the factors? It's easy to create an RSA modulus where almost no one knows the factors: for example, I can generate two 1024-bit primes $p$ and $q$ and set $n=pq$.  If I publish $n$, I will be the only person in the world who knows, or can know, $p$ and $q$.

The (now defunct) RSA Factoring Challenge numbers were generated like this:

First, 30,000 random bytes were generated using a ComScire QNG
hardware random number generator, attached to the laptop's parallel
port.
The random bytes were used as the seed values for the
B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The
public portion was exported, in DER format to a disk file.
The
moduli were extracted from the DER files and converted to decimal
for posting on the Web page.
The laptop's hard drive was destroyed.

But all of this leaves me feeling unsatisfied because--despite claims that the laptop's hard drive was destroyed--I still worry about insiders who know the factors.

Is there a method which can generate an RSA modulus so that no one knows the factors?  This might seem a ridiculous question, but we do know composites of unknown factorization.  For example, many of the largest Mersenne composites have unknown factorizations (wikipedia).

I would be fine with a multi-party algorithm and an assumption that players do not collaborate.

One practical method: use a Java Card Smart Card. Load a trivial Java applet, made with the free Java Card Classic Development Kit, that generates an RSA key, and outputs the public modulus. Then either destroy the Smart Card, or zeroize it.

The applet will be so simple that it can be convincingly audited, either from source or from the tiny, well documented Java Card bytecode (RSA key generation itself is a few bytes in that, invoking the method built into the Java Card runtime supplied by the card/micromodule manufacturer, possibly calling a library supplied by the chip manufacturer). Some Java Card models are security-certified with similar usage and security demonstration in mind (though it might be hard to purchase these certified models in small quantities, and next to impossible to obtain their full documentation).

A difficult problem: convince oneself/the audience that what's loaded in the Java Card is really the audited applet, and more generally of the integrity of the gear handling the Java Card and the result it produces. In key ceremonies for Smart Cards where the integrity of the gear is paramount, it is common to install a bare OS to a virgin PC without network access from original optical media in front of the customer, but the Smart Card readers might not be scrutinized, even though that equally matters.

Also, there still is a risk that the card developers goofed at writing the RSA key generator. There are precedents:

section 6.1.1 in Petr Švenda, Matúš Nemec, Peter Sekan, Rudolf Kvašňovský, David Formánek, David Komárek, Vashek Matyáš: The Million-Key Question — Investigating the Origins of RSA Public Keys, best paper of Usenix Security Forum 2016. This one is a Java Card (but not an audited one that I could identify from its traceability data, which I obtained from the lead author).
Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren: Factoring RSA keys from certified smart cards: Coppersmith in the wild, in proceedings of AsiaCrypt 2014. Some part of it appears to be FIPS 140-2 certified, but likely the certification was abused so badly as to become meaningless.

Ah, and of course, it is hard to convince others that the number you exhibit was produced in that way. Not such a good answer..


Having 4096 bit keys and short (< 256 byte) messages, can I simply use the key as OTP? Assumptions:

Alice and Bob use (cryptographically secure, hardware-rng generated) 4096 bit keys.
Each message is encrypted using a new key; meaning: once a key is used, it's destroyed.
Alice and Bob only need to encrypt/decrypt messages up to a length of 256 bytes.
To keep it simple, key-exchange is not part of the picture and can be assumed 100% secure.

Since the 4096 bit keys practically represent 512 bytes, the key obviously holds enough random material so that it "could" be considered suitable for One-Time-Pad use (like in classical OTP cipher examples).

Looking at the above assumptions, would the use of a simple OTP-XOR cipher indeed be secure enough from a cryptographic point of view, or is it more advisable to use another crypto-algorithm (for example a block-cipher) for some specific reason? And if, why would it be more advisable to use another cipher?

If your key material is properly random and at least as long as that which is to be encrypted, and indeed each key is used only once, then one-time pad is indeed applicable.

As was noted:

Distribution of keys will be a hard problem. OTP makes practical sense only in scenarios where keys can be distributed at some time T, then used for encrypting and decrypting messages at a later time T', when key distribution would no longer be an option. The red phone used this system (key tapes were exchanged by plane regularly).
OTP does just encryption, not integrity. You probably also need some sort of integrity check, which will need a bit more key material.

You should compute the MAC over the encrypted message, because this obviously prevent any weakness in the MAC algorithm from leaking information about the message. Also, in order to prevent an attacker from swapping messages around, the MAC should probably include a sequence number, or any other unambiguous designation for the key to use (obviously, not a hash of the key).

Alternatively, you can use a MAC over the decrypted message as long as you either encrypt it along with the message, or you use one of these nifty polynomial-based MAC which can be proven not to leak information about what they MAC. If you use OTP, you don't want to lose the psychological benefits of "proven security"...


How does a chosen plaintext attack on RSA work? How can one run a chosen plaintext attack on RSA?

If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?

Slight revision based on Paulo's remark in the comments - in a public key system a chosen plaintext attack is pretty much part of the design - arbitrary plaintexts can be encrypted to produce ciphertexts at will - by design, however, these shouldn't give any information that will allow you to deduce the private key.

A chosen ciphertext attack can be used with careful selection of the plaintext, however, to perform an attack - it's actually fairly straightforward on textbook RSA. Firstly, we have a piece of ciphertext we'll denote by:

$$C = t^e \mod n$$
Which is RSA as we know and love. Now, Eve has $C$ - this is perfectly ordinary, since Eve is supposed to be able to see $C$. Now eve has the ability to chose a plaintext - so, she choses $2$ as her plaintext and computes $C_a = 2^e \mod n$. However, to our unsuspecting victim she sends $C_b = C_a * C$, so:

$$C_b = C\cdot 2^e = t^e 2^e\mod n$$

All good so far. Now since this is a chosen plaintext attack we're reliant on having access to the decryption of our substituted value - so now the unsuspecting victim computes:

$$(C_b)^d = [t^e 2^e]^d = (t^e)^d \cdot (2^e)^d \mod n$$

However for any plaintext $x$, we know $C \equiv x^e$ and $x \equiv C^d$; so: $$(x^e)^d \equiv x \mod n$$

Therefore from the preceding result: $$(C_b)^d = t \cdot 2 \mod n$$

Hence when we get that value back, we can quite easily compute $t$. We simply need to halve it.

This can actually apply for any plaintext we wish to chose - I simply chose $2$ because I like it as a number. This paper covers the general technique and a lot more.

This only applies to textbook RSA. The proper application of RSA in the wild involves the use of padding schemes which defeat this attack by ensuring the ciphertext is not malleable in this way.


Will using a 32 character key for Blowfish make it a 32 bit encryption? I am sorry if it sounds naive but I have been searching and searching regarding what kind of encryption we end up with if we use a key of length 32 characters?

This article https://www.embedded.com/design/configurable-systems/4024599/Encrypting-data-with-the-Blowfish-algorithm explains how the algorithm works on the plaintext quite clearly but nowhere do I find the difference a key length will make.

=========Edit==========
An example of key is 996b352b-beb9-5628-a61d-4f0fbb72844e

Well, it's a kind of marketing speak.  If you look through the individual entries of this list of block ciphers, you'll see that they are categorised by two distinct parameters.

Block size. This is the number of bits that the cipher operates on at a single time. Blowfish has a 64 bit block.
Key size. Unsurprisingly, this is the length of the key.

These two parameters are somewhat independent, but key length >= block width. Blowfish's key can be up to 56 bytes, and all things being equal, the longer the key the higher the security level. Crypto guys tend to refer to bits though rather than bytes.

With reference to your question, I'd pick the longer number when telling someone about how secure my kit is. Otherwise you have to give out two numbers. You could say Blowfish128 if you want to say anything at all.

PS. Not sure if this matters to you, but the designer of Blowfish recommends using Twofish instead.

PPS. Further to some comments you've had, be aware that cryptographers would assume that your key consists of independently and uniformly distributed bytes, rather than text characters.  Please do not confuse key with password.  An error of understanding here can have very serious consequences for the security of your system.  Your example key is actually  $\operatorname{log_2}(16) \times 32 = 128 $ bits long. Modern crypto really warrants a minimum block width of 128 bits though to prevent various attacks, but that's a call only you can make.


How can I get issuerNameHash and issuerKeyHash from PEM or DER certificates? I need to get these values from pem and der files. Is there Python and C code or openssl command for these results?
Example cert in PEM format:
   -----BEGIN CERTIFICATE-----
    MIIDTTCCAjWgAwIBAgIBATANBgkqhkiG9w0BAQsFADBHMRQwEgYDVQQDDAtSb290
    IENBIFJTQTEMMAoGA1UECgwDT0NBMQswCQYDVQQGEwJOTDEUMBIGCgmSJomT8ixk
    ARkWBE9DVFQwIBcNMjAwMjEyMTgxMDI3WhgPMjA2MDAyMDIxODEwMjdaMEcxFDAS
    BgNVBAMMC1Jvb3QgQ0EgUlNBMQwwCgYDVQQKDANPQ0ExCzAJBgNVBAYTAk5MMRQw
    EgYKCZImiZPyLGQBGRYET0NUVDCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoC
    ggEBAJ0gKwiY8Yj5T+SwZCQB3evp2y65BoVdBlnL91FzpuZ1LP9i0C4dQVcjN59W
    d3lDskb9njjm41ds57zAUEesMwomFy+DfXd2zDSoBpmFCJuoW3bD+8xN1ISfrEI0
    vQPTMRtyfaue1CYo55+4Fkv0zLEbjSOx3Sl+9ciwQ4i/x6hDjclu5JXx9Bom/oR2
    +xlHZEfpGogyDvQB3al+GsOCOk9Y7kA8EaVDPLeeI+CJdOS4syoZdyEiA6cO+kAH
    0tE+Rl5Pqf3wabuO1ebTLenswa7xLrUGQ9rURmXTJQ2+23c3YsXOGgMZ5M7H2R2i
    sOt2S62t28aVs62+PwQrqh/X4vkCAwEAAaNCMEAwDwYDVR0TAQH/BAUwAwEB/zAO
    BgNVHQ8BAf8EBAMCAQYwHQYDVR0OBBYEFNSqKyVEMyNJoqivS0wO565HVoOiMA0G
    CSqGSIb3DQEBCwUAA4IBAQAtxUSnf+pb+dgLPAtLgoMLsc+CgvoeEpHF1aLWNgcc
    VSC2L0frxtpERl3xjxE9ttc+3mE6KA2UQFhf4Md4vCPf60GZw44rFl1Rj9PwrLA9
    c2AtLjcDkthhmZylgEjorzyox3wVW5pbOWRP38lDz9gpqJCzTYmmm+9skNS09/gq
    M5lYhAqBjKjLiyKylwKWdw9EOkUxnSlg4aicn83+1cdD0iNM+z6lIP5cxvQu2/f6
    8KJ9JkTofQzdyPH4l/JvuSwmXnfWR3O8JTJjAq8Z5XoqduJXhEB73Xvamdah1PB0
    BJHAh45odouHCmtG6TqRUgoFVNZDLdNurVXXzn5cnL+t
    -----END CERTIFICATE-----

Example output:
  "certificateHashData": {
    "hashAlgorithm": "SHA256",
    "issuerNameHash": "f405cb5ba4efe79d4863495e186413c551f7d98dd021030573e169146a763056",
    "issuerKeyHash": "3e1518dc6e867ea55d699922be7be6898fb5abf459709c086e17ac4760682da9",
    "serialNumber": "1"
    ]}

Expanding on what Maarten shows, openssl asn1parse can display the details, AND can also extract encoded parts of the certificate (or other ASN.1 structure):
>openssl asn1parse -i <cry87661.crt
    0:d=0  hl=4 l= 845 cons: SEQUENCE
    4:d=1  hl=4 l= 565 cons:  SEQUENCE
    8:d=2  hl=2 l=   3 cons:   cont [ 0 ]
   10:d=3  hl=2 l=   1 prim:    INTEGER           :02
   13:d=2  hl=2 l=   1 prim:   INTEGER           :01
   16:d=2  hl=2 l=  13 cons:   SEQUENCE
   18:d=3  hl=2 l=   9 prim:    OBJECT            :sha256WithRSAEncryption
   29:d=3  hl=2 l=   0 prim:    NULL
   31:d=2  hl=2 l=  71 cons:   SEQUENCE
   33:d=3  hl=2 l=  20 cons:    SET
   35:d=4  hl=2 l=  18 cons:     SEQUENCE
   37:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
   42:d=5  hl=2 l=  11 prim:      UTF8STRING        :Root CA RSA
   55:d=3  hl=2 l=  12 cons:    SET
   57:d=4  hl=2 l=  10 cons:     SEQUENCE
   59:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
   64:d=5  hl=2 l=   3 prim:      UTF8STRING        :OCA
   69:d=3  hl=2 l=  11 cons:    SET
   71:d=4  hl=2 l=   9 cons:     SEQUENCE
   73:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
   78:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :NL
   82:d=3  hl=2 l=  20 cons:    SET
   84:d=4  hl=2 l=  18 cons:     SEQUENCE
   86:d=5  hl=2 l=  10 prim:      OBJECT            :domainComponent
   98:d=5  hl=2 l=   4 prim:      IA5STRING         :OCTT
  104:d=2  hl=2 l=  32 cons:   SEQUENCE
  106:d=3  hl=2 l=  13 prim:    UTCTIME           :200212181027Z
  121:d=3  hl=2 l=  15 prim:    GENERALIZEDTIME   :20600202181027Z
  138:d=2  hl=2 l=  71 cons:   SEQUENCE
  140:d=3  hl=2 l=  20 cons:    SET
  142:d=4  hl=2 l=  18 cons:     SEQUENCE
  144:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  149:d=5  hl=2 l=  11 prim:      UTF8STRING        :Root CA RSA
  162:d=3  hl=2 l=  12 cons:    SET
  164:d=4  hl=2 l=  10 cons:     SEQUENCE
  166:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  171:d=5  hl=2 l=   3 prim:      UTF8STRING        :OCA
  176:d=3  hl=2 l=  11 cons:    SET
  178:d=4  hl=2 l=   9 cons:     SEQUENCE
  180:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
  185:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :NL
  189:d=3  hl=2 l=  20 cons:    SET
  191:d=4  hl=2 l=  18 cons:     SEQUENCE
  193:d=5  hl=2 l=  10 prim:      OBJECT            :domainComponent
  205:d=5  hl=2 l=   4 prim:      IA5STRING         :OCTT
  211:d=2  hl=4 l= 290 cons:   SEQUENCE
  215:d=3  hl=2 l=  13 cons:    SEQUENCE
  217:d=4  hl=2 l=   9 prim:     OBJECT            :rsaEncryption
  228:d=4  hl=2 l=   0 prim:     NULL
  230:d=3  hl=4 l= 271 prim:    BIT STRING
  505:d=2  hl=2 l=  66 cons:   cont [ 3 ]
  507:d=3  hl=2 l=  64 cons:    SEQUENCE
  509:d=4  hl=2 l=  15 cons:     SEQUENCE
  511:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Basic Constraints
  516:d=5  hl=2 l=   1 prim:      BOOLEAN           :255
  519:d=5  hl=2 l=   5 prim:      OCTET STRING      [HEX DUMP]:30030101FF
  526:d=4  hl=2 l=  14 cons:     SEQUENCE
  528:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Key Usage
  533:d=5  hl=2 l=   1 prim:      BOOLEAN           :255
  536:d=5  hl=2 l=   4 prim:      OCTET STRING      [HEX DUMP]:03020106
  542:d=4  hl=2 l=  29 cons:     SEQUENCE
  544:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Subject Key Identifier
  549:d=5  hl=2 l=  22 prim:      OCTET STRING      [HEX DUMP]:0414D4AA2B2544332349A2A8AF4B4C0EE7AE475683A2
  573:d=1  hl=2 l=  13 cons:  SEQUENCE
  575:d=2  hl=2 l=   9 prim:   OBJECT            :sha256WithRSAEncryption
  586:d=2  hl=2 l=   0 prim:   NULL
  588:d=1  hl=4 l= 257 prim:  BIT STRING

The SEQUENCE beginning at 31 is the Issuer name (and the one beginning 138 is the Subject name, which is the same as the Issuer in this cert because this cert is a selfsigned cert for a root CA) and the BIT STRING at 138 is the subjectPublicKey field within the subjectPublicKeyInfo substructure, which only for a selfsigned cert is the same as the issuer key, so:
>openssl asn1parse -i <cry87661.crt -strparse 31 -out cry87661.name
[snipped]
>openssl asn1parse -i <cry87661.crt -strparse 230 -out cry87661.keyx
[snipped]
>dir cry87661*
21/01/20  19:11             1,224 cry87661.crt
21/01/20  19:27               270 cry87661.keyx
21/01/20  19:13                73 cry87661.name

but these don't match your values:
>openssl sha256 <cry87661.name
(stdin)= e60bd843bf2279339127ca19ab6967081dd6f95e745dc8b8632fa56031debe5b

>openssl sha256 <cry87661.keyx
(stdin)= 89ea6977e786fcbaeb4f04e4ccdbfaa6a6088e8ba8f7404033ac1b3a62bc36a1


trying to identify the key of a vigenere cipher via brute force I'm working on a bit of an ARG game type thing that uses the vigenere cipher. what im wondering is the chance a player could brute force said cipher by simply checking all possible key sequences of the right length, that being 41 characters, for deciphering a sequence of about 1000 characters. its also using more character types than the usual 26, it has 77 unique characters. so what are the chances they could stumble across the correct key by almost (or entirely) complete luck? additionally, could i possibly make the cipher more secure by applying a secondary layer of defense (like converting to a different base or something) and thus making it harder to tell what the alphabet of the cipher is. assume the players already know that it somehow relates to a vigenere cipher and they already know the character length of the key.

If you only think about Brute Force as an attack, then we first have to compute the number of possible keys: $77^{41} = log_2(77^{41}) \approx 2^{260}$. For Brute Force this would end up in 259-260 Bit security. Common sense is, that 128 - 256 Bit security is already save. Therefore your Cipher would be secure, if Brute Force is the only possible attack and the probability for someone guessing the correct key is negligible.
On the other hand there are better attacks for Vigenere. (It took several hundred years to find efficient attacks, but today it is said to be unsecure) The Kasiski attack may be best suited to attack your cipher, because the attacker knows the length of the key.
How you may make it more secure: A secondary layer of security is in many cases not useful (either is does not archive the wanted security, it does not make anything more secure or in some cases even make security worse). Creating a good secondary layer is often difficult.  One way to make your cipher more secure is using a bigger key. If you look at the Kasiski attack the attacker needs to know the length of the key. If you use different key length this may make that attack more difficult. You could also combine bigger key length with keys of different length.


Finding k collisions on hash function Let $n$ be the size of the image-space of a hash function $H$.

It is known that you can find a collision on $H$ in $O(\sqrt{n})$ time (by birthday paradox).

How can I show that, in order to find $k$ collisions, it is needed only $O(\sqrt{k\times n})$ time?

I have no idea yet... I guess this happens because after you look $O(\sqrt{n})$ times for collisions, the probability grows significantly, but I don't know where I can apply $k$.

I will try to give a simple proof of the expectation. Define $W_t(n,p)$ as the expected number of trials required  to find the $t^{th}$ collision in a set of size $n$ with probability $p.$

Normally, for $W_1(n,p),$ the standard birthday problem with fail probability $p,$ which gives $W_1 = c \sqrt{n},$ with $c$ obtained by solving
$$
\exp\left(\frac{-k(k-1)}{2n}\right) = p = \exp( \ln(p))=\exp(-\ln (1/p))\tag{1}\label{eq1}
$$
for $p=1/2,$ and letting the $k$ obtained to be $W_1(n,p).$

So we're after the total expected wait, call it $$T_k=W_1(n,p_1)+W_2(n,p_2)+\cdots+W_k(n,p_k)$$
 with the assumption that $k$ is much much smaller than $n.$ Let $W_i$ denote the expected wait for the $t^{th}$ collision with probability $p_t,$ which we shall select later.

Solving $\eqref{eq1}$ approximately gives
$$
W_1(n,p)= \sqrt{2 \ln(1/p) n}.
$$
Now note that,
$$\begin{align}
W_t(n,p) &=\frac{n}{n-t+1} W_1(n-t+1,p)\\
&=\frac{n}{n-t+1}\sqrt{2 \ln(1/p) (n-t+1)}\\
&=O\left(\sqrt{2 \ln(1/p) (n-t+1)}\,\right),
\end{align}$$
(both sides are expectations)
since there are already $t-1$ collisions and $t$ is much smaller than $n.$
To explain further, this means that you want the next collision in the remaining $n-(t-1)$ positions but the probability of falling into one of those positions is $q=(n-t+1)/n$ so it takes an expected $1/q$ trials.

Now we can write
$$
T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(1/p_t) (n-t+1)}\right),
$$
but due to the multistage nature of the argument, the overall probability that this sequence of waiting times fails to find the $k$th collision is the product
$$p_1p_2 \cdots p_k.
$$
We want this probability to be $1/2,$ as in the original birthday problem, which we can ensure by choosing $p_t=(1/2)^{1/k},$ for all $t.$ This can be optimized a bit by putting slowly falling probabilities on later epochs and keeping the product of the probabilities fixed, but it won't make a difference to the $O(\cdot)$ answer. Since $\ln(2^{1/k})=k^{-1}\ln 2,$ we have

$$
T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(2) k^{-1}(n-t+1)}\right)=
\sqrt{k} \times O\left(\sqrt{ (n+1)}\right),
$$
which gives (since there are $k$ terms in the sum and a $k^{-1/2}$ multiplying each term)
$$
T_k=O(\sqrt{nk})$$
as required.


Data decrypted, but unwanted characters in the beginning I am a bit new at cryptography, I tried to recover data from an old app database, I got the key and the type of encryption, it says "AES/CBC/PKCS5Padding", I used this online tool http://8gwifi.org/CipherFunctions.jsp to decrypt some strings, it decrypted but I got some characters at the beginning of my data, for example:

2cjABhgd?????samsung

?9??kj`?D g?GALAXY S5

In that case I should only get "samsung" and "GALAXY S5", but for some reason I get characters at the beginning. I want to know why this happens and how can I automatically get rid off those characters of the beginning, because I have hundreds of lines of data that decrypts like this.

If the data at the beginning is exactly 16 characters long every time, then it is certainly the initialization value for the CBC mode, and you can simply cut them off and output the valid data starting at byte 17.

My guess is that because that web decoder provides no specific input for the IV, it does not attempt to truncate the prefix itself, and simply outputs all the data, letting you decide what to do with it.


AES CBC: Use hash of key as IV when every key is unique? I have an app that uses a different random key for every file that is being encrypted.

Am I correct in assuming that this means that I can safely use a hash of the random key as the IV, because that would also lead to a unique IV?

If possible, I would prefer to not store the IV along with the file for performance and storage reasons. OTOH, I obviously don't want to compromise on security...

Thanks for your advice

Yes, that would be an excellent idea, at least if you use a cryptographically secure hash that has output indistinguishable from random. That's however true for most secure hash algorithms out there. You could - for instance - use SHA-256 and then take the leftmost 128 bits; using the leftmost bits is more or less the industry standard.

You cannot derive the key if the IV gets known because the hash is one way, and an adversary cannot predict the IV because to do that the key should be known. One possible issue is that hash algorithms are not always protected against side channel attacks. Then again, most hash algorithms are not directly susceptible to them either.
Beware that you should document that the resulting IV is static, if you ever start reusing the keys then you'd be in trouble.

Alternatively you could use a KDF to derive two values from a master secret, say S. For instance, you could use K = KDF(S, "Key", 128) and IV = KDF(S, "IV", 128) to derive both the encryption key and the IV from one input value.

K | IV = KDF(S, "KeyAndIV", 256) is also often used - it is for instance similar to key derivation in TLS 1.2. This is provably secure and may require less computation time than doing the KDF twice.

The resulting key and IV when using a KDF over a secret value do not depend on each other. This is more secure than having the IV being dependent on the key. A good KDF for key based key derivation (KBKDF) is HKDF.


What is the difference between strong/weak alignment? In this answer there is the mention of "weak alignment", followed by an indication that it is related to "resistance to truncated differential cryptanalysis".

What exactly is the difference between strong versus weak alignment?

How does it provide resistance to truncated differential cryptanalysis, and does it influence strength or weakness against any other techniques?

What ways can weak alignment be obtained? For example, is there a way to convert AES to have weak alignment (and would that be a good thing?)

Truncated differential cryptanalysis was introduced by Lars R. Knudsen at FSE 1994.

The Keccak team provides an summary of this technique as follows:

  In truncated differential cryptanalysis one divides the function input, output and intermediate computation values in sub-blocks, typically of equal size (e.g. bytes). Whereas in classical differential cryptanalysis one studies propagation of differences that are fully specified, in truncated differential cryptanalysis one only specifies whether a sub-block is active (has a difference) or is passive (has no difference).

It has been applied by J. Daemen and V. Rijmen on AES, the idea is therefore to indicate if a byte has a been modified or not in order to retrieve a distinguisher.

In the case of a strong alignment, the truncated differences can be easily constrained and followed. In the case of a weak alignment, differences spread extremely fast and it makes really hard for a subdivision of the input space to be found.

On Keccak ($\iota \circ \chi \circ \rho \circ \pi \circ \theta$) we ignore the $\iota$ operation as it is irrelevant from a Xor difference point of view. Lets consider a subdivision of 5 bits (due to the size of the somewhat S-box substitution: the $\chi$ function) and assume we have a difference on that group.

We will ignore $\theta$ due to its operation being difficult to visualize, basically, the active difference is spread over the slice and the slice behind  (by $z$ coordinate) in the state.

Then we have $\pi$, if a truncated difference of 5 bit is active then the slice will be set to active.

.

So now we have 5 active truncated difference to track.

Then we have $\rho$, which spreads the differences among the $z-axis$ :

Thus, the active truncated differences are now 25.

In other word, the number of active truncated difference in Keccak increases really quickly $\mathcal{O}(25^n)$. This what we call a weak alignment.


AES S-box and Nothing Up My Sleeve Cryptographic primitives should have nothing-up-my-sleeve property to prove their designers don't have an advantage in using them versus the general public.

For example, Blowfish is using binary reprensentation of digits of π to initialize its key schedule. The Salsa20 family of ciphers use the ASCII string "expand 32-byte k" as constants in its block initialization process.

Now, my question is about widely used AES cipher. I cannot find any references to how its S-boxes were generated. Recently, it was proven that a Grasshopper block cipher S-boxes were generated using a hidden algorithm and that this made it potentially weaker.

So, does this mean AES doesn't have nothing-up-my-sleeve property? Can designers of AES have an advantage in using it?

So, does this mean AES doesn't have nothing-up-my-sleeve property?

That is correct in a sense, the design of the s-box is formulaic. It is generated using finite field inversion, an affine transform, and xor of a constant (0x63). It can be described as a simple equation.

The other parts of round transformation also have a very simple description, the most complex being the MixColumns operation.

The key schedule adds a round constant which is generated simply by consecutive multiplication by 2 in a finite field.

Not using NUMS numbers allows the entire encryption operation to be described as an equation in a much more simple manner, and is easier to analyze. Rational is given for all choices of constants, although some seem.. incorrectly chosen, like the s-box constant, which causes a self-inverse mapping (see my comment on answer). A limited number of specifically chosen constants also prevents anything from being hidden in the same manner NUMS numbers do.


Find the key to a Vigenère cipher, given known ciphertext and plaintext I have the ciphertext and the plaintext. Is it possible to know the key? If not, what do I need to find it?

Yes.

Remember that, in a Vigenère cipher, the $n$-th ciphertext letter is calculated by adding the $n$-th plaintext letter and the $n$-th key letter (where the key is repeated as many times as necessary to make it as long as the plaintext) modulo 26 (for the standard English alphabet), i.e.:

$$c_n \equiv p_n + k_n \mod 26 \tag1$$

(Here, I'll assume the usual conversion between letters of the alphabet and numbers modulo 26, i.e. $\rm A = 0$, $\rm B = 1$, $\rm C = 2$, $\dotsc$, $\rm Z = 25$.)

Conversely, to decrypt the message, the key is subtracted from the plaintext: $$p_n \equiv c_n - k_n \mod 26 \tag2$$

Note that the decryption rule $(2)$ is obtained from the encryption rule $(1)$ by simple algebraic manipulation: we merely need to subtract $k_n$ from both sides of the equation.  Conversely, if we know $p_n$ and $c_n$, we can solve for $k_n$ simply by subtracting $p_n$ from both sides of $(1)$:

$$k_n = c_n - p_n \mod 26 \tag3$$

Note that similarity to the decryption rule $(2)$.  Basically, to find out the key, given the ciphertext and plaintext, you simply need to decrypt the ciphertext using the plaintext as the key.


Why won't a BFT protocol using simple signing/voting work? PBFT and most consensus algorithms are more complicated than a simple voting scheme. By simple voting I mean the following: we require all nodes to sign their local copy of the state and send this signed message to all other nodes. Each node then collects messages from all other nodes, and accepts the state if more than t < n nodes agree on the same state.

There are many ways to achieve the scheme above (e.g., each node individually signs, or using threshold signatures), which seems much simpler than other protocols such as PBFT (which among other things, requires designating a leader).

Therefore, I'm left to assume that voting can't directly produce a secure BFT protocol, but my question is - why is this the case? Where does consensus by voting break?

The purpose of a BFT is to achieve Byzantine Fault Tolerance rather than to be cryptographically secure. In fact, some BFT papers have no cryptography in them at all. You could devise a secure voting scheme but that doesn't automatically make it tolerant to byzantine failures.

Generally these algorithms seek to achieve liveness (eventual consistency of the data) and safety up to a certain number of faults, neither of these premises are present in your voting example. If you can guarantee through your protocol that even in the presence of a certain number of byzantine nodes (t < n) the protocol reaches consensus on a consistent state, then you have just created a BFT protocol.


Need help to understand this RSA common modulus attack Python code I am reading Practical Cryptography in Python. I have problem understanding the common_modulus_decrypt() function. I think the prerequisite of RSA Common Modulus Attack is that two public exponents have to be co-prime, meaning $gcd(e_1,e_2)=1$, right? That is what I get from how to use common modulus attack?

If this is true, why does it do the following:
def common_modulus_decrypt(c1, c2, key1, key2):
    key1_numbers = key1.public_numbers()
    key2_numbers = key2.public_numbers()

    if key1_numbers.n != key2_numbers.n:
        raise ValueError("Common modulus attack requires a common modulus")
    n = key1_numbers.n

    if key1_numbers.e == key2_numbers.e:
        raise ValueError("Common modulus attack requires different public exponents")

    e1, e2 = key1_numbers.e, key2_numbers.e
    num1, num2 = min(e1, e2), max(e1, e2)
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    gcd = num1

    a = gmpy2.invert(key1_numbers.e, key2_numbers.e)
    b = float(gcd - (a*e1))/float(e2)

    i = gmpy2.invert(c2, n)
    mx = pow(c1, a, n)
    my = pow(i, int(-b), n)
    return mx * my % n

If gcd is always 1, why bothering with the while loop above? Also, I thought it should use the Extended Euclidean algorithm to get a and b. Why is it doing invert with e1 and e2? Why is it using float()?
The last 3 steps for i,mx,my I can understand, as it assumes b is a minus value.

Step by step of the code;

$gcd = \gcd(e_1,e_2)$

$a = e_1^{-1} \bmod e_2$

$b =gcd - (a\cdot e_1))/e_2 \implies gcd = b \cdot e_2 + a\cdot e_1$; The Bézout's identity

$i = c_2^{-1} \bmod n$

$mx = c_1^a \bmod n$

$my = i^{-b} \bmod n$

$\text{return } (mx \cdot my) \bmod n$

Now check
\begin{align}
 mx \cdot my &=c_1^a \cdot i^{-b} \pmod n\\
  & = c_1^a \cdot (c_2^{-1})^{-b} \pmod n\\
  & =(m^{e_1})^a \cdot (m^{e_2})^{b} \pmod n\\
  & =(m^{e_1 a+ e_2 b}) \pmod n\\
  & = (m^{gcd})  & & \big[ = m \!\!\!\pmod n \,\textbf{ if } gcd=1\big]\\
\end{align}
The above calculation works for any $gcd$. This doesn't mean that we can resolve the message $m$ if $gcd>1$. What if $gcd \neq 1$ then for case 2, it is so-called Rabin Cryptosystem, security is shown to be equal to factoring. if $gcd =3$ is the cube-root attack possible and if the textbook RSA is used and the message $m < \sqrt[3]{n}$ recovery possible, and so on.
The conclusion is that they forget to write
  if gcd != 1:
      return -1

Writing good software is hard, writing good cryptographic software is much harder.
or someone is wrong on the internet

The common modulus attack is performed on Text-Book RSA when Alice and Bob use the same modulus $n$ with different public modulus. The first observation is that this is dangerous since Alice can learn Bob's private key, v.s. On the other hand, the eavesdropper ( passive attacker) knows the public keys $(n,e_1)$ and $(n,e_2)$ and when observed that the same message is sent to Alice and Bob (possibly broadcasting). Then the eavesdropper can resolve the broadcasted message $m$ if $\gcd(e_1,e_2)=1$. If they are using the same public exponent, this attack doesn't work.
When proper padding is used like PKCS#1 v1.5 and OAEP then this attack is not possible since they use randomization that prevents the equality of the same messages.


Secure Channel - Encryption and Decryption Keys For A Message I'm currently reading Cryptography Engineering and in Chapter 7, the topic of secure channel is discussed.

The channel described is using CTR for encryption. Below I include images with pseudo-code used in the book (source):

In Secure Channel: Initialization, 4 different keys are generated (assuming no collisions).

In Secure Channel: Sending a Message the key stream is generated using KeySendEnc as the key to the encryption function (let's say we're using AES here). Then, what we do is XOR the message we want to encrypt (plaintext || authenicated plaintext) with the key stream generated in the previous step. To authenticate the plain text, KeySendAux is used. Up to this point, everything makes sense.

Now, in Secure Channel: Receiving A Message, KeyRecEnc is used as the key to generate the key stream k. Then, the encrypted message is XORed with this k to obtain the original message (plaintext || authenicated plaintext). If KeyRecEnc ≠
 KeySendEnc, then the key stream k, generated in the two cases is different. My question is exactly here, how do we obtain the original message if we XOR the ciphertext with some other key stream, different from the one that we used to encrypt the message in Secure Channel: Sending a Message.

Then, KeyRecAuth (KeyRecAuth ≠ KeySendAuth) is used to obtain a MAC. This MAC is then compared with the received MAC (after it's decrypted). How can those two MACs can ever be the same (ignoring collisions), since the input to the HMAC-h function is different in both cases (because KeyRecAuth ≠ KeySendAuth).

Thanks in advance.

how do we obtain the original message if we XOR the ciphertext with some other key stream, different from the one that we used to encrypt the message in Secure Channel: Sending a Message?

Answer: we don't use different keystreams.  When Alice sends Bob a message, she uses the 'Enc Alice to Bob' keystream,  When Bob receives that message, he uses that same 'Enc Alice to Bob' keystream.  The 'Enc Bob to Alice' keystream is used for messages that Bob send to Alice (both by Bob to encrypt those messages, and by Alice to decrypt those messages).

The MACs work the same way; the 'auth Alice to Bob' MAC keys are used by both sides to do integrity checking on the messages that Alice sends to Bob, and the 'auth Bob to Alice' MAC keys are used by both sides for messages that Bob sends to Alice.


For TLS AES_CCM mode how does CBC_MAC work when the message length is not aligned to block size? Even after goign through lot of specs I failed to understand how CBC-MAC works, specifically in case we have message not aligned to 16 bytes. Are there any padding bytes?

See RFC 3610, 2.2 Authentication (page 3):

  The message blocks are formed by splitting the message $m$ into 16-octet blocks, and then padding the last block with zeroes if necessary.


Noise in Homomorphic encryption What is the noise in homomorphic encryption schemes? (or where does the noise come from, I see that its inbuilt in the scheme and is not a side channel or disturbance noise)

Is it also due to the noise that HE is a probabilistic scheme ?

The noise is usually a small term added into the ciphertext while encrypting.

This term may be a small integer (if the scheme is based on integers) or a small polynomial (if the scheme is based on polynomials), etc.

How to decide if a term is small or not depends on the security and correctness properties of each system (for instance, a polynomial is typically considered small if all its coefficients are small).

This noise is added to guarantee the security of the cryptosystems and is sampled from a distribution of small terms (for instance, from a set of polynomials with coefficients in $\{-1, 0, 1\}$). Therefore, the noise is random. So, it implies that the HE scheme is probabilistic, but, in general there are other random values involved in the encryption process, so, I don't know if it is right to say the probabilistic property is due to the noise... (But I hope you got the point).

The decryption function does not work if the noise is greater than a certain maximum value (each scheme with each set of parameters used has its own limit) and the homomorphic operations increase the noise, that is the reason the number of operations is usually limited and there are several techniques to control the noise growth.

As an example, take the symmetric "toy-scheme" from Fully Homomorphic Encryption over the Integers:

the integer $p$ is the private key.
to encrypt a bit $m$ into a (big) integer $c$, we sample integers $q$ and $r$ and do $c = pq + 2r + m$.
to decrypt $c$ we do $c \mod p$, wich gives us $2r + m$ if $2r + m$ is smaller than $p$, then we reduce $\mod 2$, ending up with $m$.

Do you see that if $2r$ is bigger than $p$, then decryption will not work? (because reducing mod $p$ would not result in $2r + m$ in this case). So, this $2r$ is the noise in this scheme.

Note that taking $c_0 = pq_0 + 2r_0 + m_0$ and $c_1 = pq_1 + 2r_1 + m_1$, we have

$c_0 + c_1 = p(q_0 + q_1) + 2(r_0 + r_1) + (m_0 + m_1)$

which means a addition increases the noise. The multiplication also does so (take a look on the paper).

Therefore, since each operation increases the noise and there is a maximum acceptable value for the noise, the number of operations is limited.


Is there a 1:1 mapping between private and public EC keys? After asking: Are all possible EC private keys valid? I learned that all 32 byte (256 bit) values greater than 0 and less than n are all valid private keys.  This means that 99% of all 256 bit values are valid private keys.  (This was a revelation to me.)

The public key space is 257 bits, as it includes X and the sign bit of Y.

Is there an exact 1:1 mapping between private and public keys?

Is there a way of telling whether a 257 bit value is a valid public key? (i.e. that a private key maps to it, as slightly more than half of all 257 bit values must not be valid public keys, if there is a 1:1 mapping.)

(I'm using secp256k1.)

Thanks for your answers.

My mental model, for an imaginary curve with n = 5, a 3 bit private key and 4 bit public key now looks like this:

private              public
0x0    +-----------> 0x0
0x1 ---+             0x1
0x2 -----------+     0x2
0x3 ---------+ |     0x3
0x4 ---+     +-|---> 0x4
0x5    |       |     0x5
0x6    |       |     0x6
0x7    |       |     0x7
       |       |     0x8
       |       +---> 0x9
       |             0xa
       |             0xb
       |             0xc
       |             0xd
       |             0xe
       +-----------> 0xf

Points on secp256k1 fulfill the equation:

$$ y^2=x^3+7 \pmod p$$

Your 257 bit compressed point consists of the sign* of $y$ and the value of $x$. You probably want to restrict $x$ to $0 \leq x < p$ as a canonical representation.

Since $y^2$ is obviously a square,  we need to look at $x^3+7$ to see if it's a square as well:

If $x^3+7$ is a square, then there are two points for that $x$ which only differ by the sign of $y$, which is why the compressed point contains the sign of $y$.
If $x^3+7$ is zero, there is only one solution, since $y=-y$.
If $x^3+7$ is a non-square, then there are no solutions.

Not counting $0$, exactly half the elements of the finite field are square and the other half is non-square. $x^3+7$ complicates matters a bit, so approximately half of the possible $x$ values are square. Hasse's theorem on elliptic curves quantifies this approximation.

You can efficiently check if a field element is square, and thus verify if it is a valid $x$ value of a point on the curve.

* field-elements don't actually have a sign. But since the least significant bit of non-zero values differs between $+y$ and $-y$, we can use it as sign. See Determine if a public key point y is negative or positive, odd or even? for a longer explanation.


Is there any benefit of changing the AES-CCM encryption key periodically even if the Nonce space is not exhausted yet? I would like an answer that could be sustained by a mathematical proof.

Let's say I'm using AES-CCM to encrypt a lot of messages, and I always use a different nonce.

I know that when the nonce space gets exhausted, the encryption key needs to be changed.

The question is: even though my encryption key has not been compromised and the nonce space is not exhausted, do I have any benefit from changing the encryption key at random times?

My intuition is that whenever I encrypt some data and someone can see the result of the encryption, I somehow "lose" a tiny bit of entropy, even though I change the nonce every time. So, by changing the encryption key at some point, it feels like I'm gaining because the attacker has never seen messages encrypted with this key before.

Is it really worth the effort of changing the key periodically or is assuring an unique nonce really enough?

CCM mode uses CTR mode the encryption and CBC-MAC for the authentication. For a security proof you can refer to On the Security of CTR + CBC-MAC.

With CTR the fact that AES is a PRP rather than PRF starts to show after $2^{64}$ blocks have been encrypted. In practice this does not lead to a very effective attack even then.

After a similar number of blocks encrypted, collisions could allow MAC forgeries for new messages. This is a much more serious attack, though it of course requires an active adversary to take advantage of it. To keep the probability of collisions low it is sometimes recommended to use similar authentication modes (e.g. CMAC) for only $2^{48}$ blocks.

Note that the above limit is not dependent on the nonce size, which for CCM is usually e.g. 12 bytes, but the block size of the cipher which for AES is 128 bits (16 bytes). (With random nonces a nonce collision would be likely earlier than the above.)

In practice, you can rest easy while using the same key for gigabytes or even terabytes of data. Only if your get into petabyte range does key lifetime become a concern. However, the above attacks are probabilistic and if you can frequently agree on a new key, you get lower probabilities.


AES standard C library implementation I'm working to implement AES (128/256 - either) on one of the RISCV ISA processors & later improve performance by introducing a custom instruction in RISCV ISA.

I'm a crypto newbie and plan to use the
NIST test vectors to validate this C code.

I need to know the below things

1) Is there a link wherein i can find implementation of AES using standard C library ?

2) Do i have to use some hashing scheme along with AES ?  If yes, which one ?

3) Is it a good idea to validate my AES C code  with the NIST test vectors

4) Do you recommend using a encryption library instead ? If so where can i find it ?

Don't roll your own. (AKA: The first rule of cryptography.)

Do not create your own cipher, do not implement a cipher.

  Is there a link wherein i can find implementation of AES using standard C library ?

You can find a C implementation of AES in The Design of Rijndael, Section E, page 221. Test vectors are also provided in Section D. However, it is not recommended to use this implementation because it is vulnerable to
cache timing attacks:

Cache-timing attacks on AES.: Dan J. Bernstein
Cache Attacks and Countermeasures: the Case of AES, Dag Arne Osvik, Adi Shamir and Eran Tromer
Faster and Timing-Attack Resistant AES-GCM: Emilia Kasper and Peter Schwabe

  Do i have to use some hashing scheme along with AES ? If yes, which one ?

You need a hashing scheme only if you want to provide authenticity/integrity (see MAC schemes, for more reading about this see here).
Thus having a hashing scheme along is completely independent to having your AES implementation. You might however want to have a look at AES with GCM, EAX or CCM  to provide authentication.

For hashing function, if you go by the standards, it is advised to use at least SHA-256 or even better SHA3-256 (as specified in FIPS 202 by the NIST).

  Is it a good idea to validate my AES C code with the NIST test vectors

It is more than a good idea. It is required. However, making your implementation work and produce the same results as the test vectors does not guarantees you that your implementation is correct (it does still provide you a strong confidence that your code might be correct). You have to check that every parts of your implementation matches the specifications of the algorithm.

  Do you recommend using a encryption library instead ? If so where can i find it ?

Using a encryption library is highly recommended. It will prevent you from suffering from cache timing attacks and other nasty things. It also guarantees that the code is correctly implemented. As for which library to use, at the time of the post (October 2016), you can have a look at OpenSSL, Libsodium or NaCl.


How to add passphrase to an RSA key? If I want to protect a private RSA key, do I just XOR the password into the key, or do I do something else? Is it secure?

Edit:
I got a good answer from a comment - Hash the password/passphrase with PBKDF and use that as a key for AES to encrypt the RSA private key. Also the passphrase is never stored on the disk. The user is prompted to enter it when starting the programm and it is stored in RAM for a limited amount of time(It will be overwritten later and RAM is cleared anyway on shutdown.)

First things first: Don't roll your own crypto.

As for your current approach: This is basically a vigenere cipher which is inherently broken, provides not integrity protection and wouldn't even encrypt known / predictable bit positions (where the ASCII code is constant zero or one).

As for an improved version:
Use a well-known encryption algorithm (e.g. AES-GCM) to encrypt and authenticate the key. Don't forget that you have to use a nonce (a number used only once) with it. Do not feed the user password directly into the cipher, but rather feed it into a proper password based key derivation function (PBKDF) (e.g. Argon2, scrypt, bcrypt, PBKDF2). Make sure you use a salt and that it is random and that the derivation parameters are so large that key access takes about 100ms of full CPU load on your system.


Any historical accounts of cryptanalysis of Jefferson's wheel cipher? David Kahn in his book "The Codebreakers" wrote about Jefferson's wheel cipher, saying
that

  To this day the Navy uses it…

(the book was first published in 1967)
Are there any historical accounts of successful cryptanalysis of that cipher?

Wikipedia gives an answer although it provides no reference.

The Bazeries cylinder was a relatively strong system at the time (compared to many other systems in use), and Etienne Bazeries, a competent but very opinionated man, is said to have regarded it as indecipherable. In fact, it is hardly impregnable, and the "Pers z" code-breaking group of the German Foreign Office cracked the M-138-A in 1944. However, by that time the Americans had much more sophisticated cipher systems in operation. Many of the decrypts of Allied communications presented to the German high command were disregarded, because all they did was confirm bad news that nobody wanted to acknowledge in an environment where defeatism was potentially a capital crime.
de Viaris (aka Marquis Gaetan Henri Leon Viarizio di Lesegno) who is famous for one of the first printing cipher devices (1874), solved the Bazeries cylinder in 1893, so Bazeries alleged confidence in the system was ill-placed.
One major weakness of the Bazeries cylinder is that the offset from the plaintext letter to the ciphertext letter for the cipher alphabet on each disk will be exactly the same.

It intuitively seems easy to brute-force with a partially known plaintext. The chance that two disks will have the same distance from $C_i$ to $P_i$ is negligible. You then brute-force the possible outcomes and compare them against a dictionary. You've arrived at a small subset of possible plaintexts so you select the one that makes more sense. A second message coded with the same key will verify the results.


What are some design considerations for S-Boxes? My studies in cryptography have been quite detailed so far, however, one area that hasn't been explained to me is how S-Boxes are typically designed. Typically, the S-boxes are provided "as is" by the developers of the algorithm, but I am looking for information on what type of considerations cryptographers evaluate when they design an S-box. Are the numbers in the lookup table chosen at random? Are they generated mathematically? If so, what are some types of maths used and why? Feel free to choose an example cipher or two in your explanation.

The main consideration is to ensure no strong differential or affine properties.

Random S-Boxes are actually not bad in this regard though not necessarily optimal.

However Most would not trust "Random" S-boxes and prefer a Nothing-Up-My-Sleeve choice. For fear the designer may have cleverly selected the values to enable some unknown attack. We want some plausible explanation for why the specific values were chosen.

The AES S-boxes are such, they were selected based on a simple mathematical formula, and yet can be shown to be fairly resilient to differential and linear cryptanalysis.


Is there a zero knowledge proof for divisibility by 7? For a demonstration, I would like to present a zero knowledge proof that one party has a secret number that is divisible by 7. The goal is to prove that they have such a number without releasing the number.

Is this a reasonable thing to prove with a zero knowledge system? If so, how would I go about doing it?

For bonus points, I'd like to demonstrate it with a non-interactive zero knowledge proof.

Everyone has access to a number divisible by 7, like 0, 7, 21, 434, etc, so I will assume you mean there is a secret that a party has and is using and THAT number has to be divisible by 7.

  Is this a reasonable thing to prove with a zero knowledge system?

It does seem rather odd, but if the other party needs to be sure your secret is divisible by 7, then you need this proof.  I can't imagine such a protocol off the top of my head, but if you have one that requires it, then I guess you need it.

You can do this in Zero Knowledge if you are willing to concede pieces of information that are usually considered minor.  You can prove anything problem in NP in zero knowledge.  It would imply knowledge of the divisor, but if you know the secret number, you can already the number divided by 7.  By the nature of the cryptographic tools, you will be forced to place an upper bound on the size of $n$ and $n \over 7$.  There is also the issue of overflow.  In many cryptographic settings, $n \over 7$ could be large enough so that if you were to multiply by 7, it would wrap around and reach some normally unrelated $n$.

If $n$ is divisible by 7, then there is an integer $k = {n \over 7}$

You can encrypt $n$ and the $k$ in exponential (additive) elgamal or use Pedersen Commitment, all of which are homomorphic.  I will use Pedersen Commitments.  With a group $G$, take generators $g, h \in G$ such that the DLOG between $g$ and $h$ is unknown.   and $r_x$ be random numbers.  $q = |G|$.

This proof consists of two distinct parts:  First, we prove that $7k \equiv n
 \text{ mod } q$, then we prove that $7k < q$.

The Prover creates two commitments $C_k = g^k h^{r_k}$ and $C_n = g^n h^{r_n}$ and sends them to the Verifier.
The Verifier and Prover raise ${C_k}^7 = g^{7 k} h^{7 r_k} = {C_{7k}}$.
The Verifier and Prover computes $C_{7k} \cdot {C_n}^{-1} = g^{7k - n} h^{7r_k - r_n} = h^{7r_k - r_n}$.
The Prover privately calculates $r_1 - 7r_0$
The Prover and Verifier run Schnorr's protocol on $C_{7k} \cdot {C_n}^{-1}$, with the Prover proving knowledge of the DLOG of $h^{r_n - 7r_k}$ base $h$.

NOTE:  At this point, it is proven that $k \equiv {n \over 7}$ mod $q$, but it is not proven that $k$ didn't overflow, meaning at this point $7k$ could be greater than $q$, meaning in $n = 7k \text{ mod } q$, $n$ may be divisible by $k + q$ instead of $k$.  The following steps prove $7k$ didn't overflow by representing it in a bitwise manner, essentially setting bounds on $k$ based.  This implicitly puts an upper bound on the value of $0 \leq k \lt 2^t$, where $t$ is the number of bits.  You can have as many leading zeroes as you need if $k$ is small.

If the Verifier accepts the Schnorr proof, the Prover creates a bitwise representation of $k$.  The Prover constructs a list of $t$ bit commitments representing $k$, of the form $C_{b_i} = g^{b_i} h^{r_i}$, where $b_i$ is the bit in the $2^i$ place in $k$.  $t$ has to be 4 bits less than the number of bits (or fewer) in the order $q$ to avoid overflow and to leak as little information as possible, as multiplying will add 3 total bits to the number.
Prove each commitment hides a bit.  There is a proof for this in the appendix of this paper: http://crypto.stanford.edu/~dabo/pubs/abstracts/provisions.html.
If these proofs are accepted, both parties homomorphically combine the bits to get a commitment of $k$:  $C_k' = \prod_{i=0}^{t} {C_{b_i}}^{2^i} = g^k h^{r'_k}$. The Prover knows $r'_k = \sum_{i=0}^t r_i \cdot 2^i$.
The Verifier and Prover computes $C_{k} \cdot {C_k'}^{-1} = g^{k - k} h^{r_k - r'_k} = h^{r_k - r'_k}$.  The Prover calculates $r_k - r'_k$.
The Prover and Verifier run Schnorr's Protocol to prove knowledge of the DLOG of $C_{k} \cdot {C_k'}^{-1}$ base $h$, which happens to be $r_k - r'_k$.

This protocol does release some information about the secrets, namely $n < 7\cdot 2^t < q$, ${n \over 7} < 2^t$, but usually with this kind of proof, the Prover is willing to concede these points.  You can get more precise by using a range proof to prove that $k < \left \lfloor{q\over 7} \right \rfloor$ on steps 6 and 7, but you can find that on your own.  Other than these pieces of information, this protocol should be Zero Knowledge.

This protocol perfectly hides $k$ within the bounds above.  Any $k$ within those bounds can produce an identical transcript.  Even with infinite computational power (assuming true random numbers), an adversary can not figure out your $k$ afterwards.  Same mostly goes for $n$, except they know $n$ is divisible by 7.

It should be noted that nothing here makes the Prover use the appropriate $n$.  This will need to be either verified beforehand.  If you don't care which $n$ he chose, he is still bound to using the $n$ from this proof if you use the appropriate Zero Knowledge Proofs to require he use the $n$.

This protocol can be made non interactive by taking the component Zero Knowledge Proofs and applying the Fiat-Shamir Heuristic, which replaced the Verifier's challenge with a hash of the inputs and the initial communication.

There is also the logic circuit option, which is more flexible but less efficient.  You essentially prove your bits from the $k$ can go through a multiplication logic circuit and end up with $n$.

If you haven't read it yet, I would recommend reading Hazay and Lindell's section on Zero Knowledge Proofs from the book Efficient Secure Two-Party Protocols: Techniques and Constructions (Information Security and Cryptography)


Do public/private pairs work both ways? Public/private key algorithms such as RSA encrypt a message with a private key but only decrypted with another (mathematically related) key.

Can the public key decrypt the messages encrypted with the private key and the private key decrypt messages encrypted with the public key?
If the algorithm is based on multiplying two big numbers this seems possible. However, I'm not sure.

Well, first of all, the answer to your question depends quite a lot on whether your asking about RSA specifically, or public key algorithms in general (of which RSA is one example).

For raw RSA, the core operations to convert between the plaintext $M$ and the ciphertext $C$ is:

$C = (M^e) \bmod N$

$M = (C^d) \bmod N$

where the private key is the pair $(N, d)$ and the public key is the pair $(N, e)$.  At this very high level, it is obvious that the operation is symmetric, and there's no inherent reason why one couldn't "encrypt" with the private key, and "decrypt" with the public (although "encryption" isn't quite the correct terminology if anyone can decrypt it).

However, it is rarely appropriate to use raw RSA as such; RSA has a homomorphic property that can easily leak information.  To avoid such weaknesses, we generally perform padding before and after.  So, for RSA public key encryption, we usually do:

$C = (Pad(M)^e) \bmod N$

$M = Depad( (C^d) \bmod N )$

and for performing signature operations, we do:

$C = (Pad(M)^d) \bmod N$

$M = Depad( (C^e) \bmod N )$

Now, it still looks symmetric; however, the security properties we need for the Padding operation differs between public key encryption and signatures.  For example, we don't care if an attacker can use the homomorphic properties to cobble together a valid looking $Pad(M)^e$ value; we rather assume that he can compute that directly.  However, we have to ensure that, for a signature, he absolutely cannot cobble together a valid looking $Pad(M)^d$ value.

The bottom line: if you want to use RSA to perform signature operations (which is what people usually mean when they ask about 'encrypting with the private key'), you should look at PKCS #1, and do what it says; it's subtler than it looks.

On the other hand (going back to your original question), if you're asking about public key algorithms in general, well, no, you can't usually "encrypt" with the private key; RSA is about the only public key algorithm that can be described as doing signatures that way.  Other algorithms (such as DSA) work entirely differently.


How exactly does certificate based authentication work? I know the concept of key generation, as well as encryption and decryption using public and private keys.

When it comes to authenticating a user by a server, in general there are three types:

password based,
certificate based, and
hybrid (encrypting the symmetric key using asymmetric algorithm).

I am a bit confused how exactly the second type (certificate based) works using nothing but a certificate and I'm a bit unsure about how exactly it works. Can anybody tell me what is being sent from the user's side for getting authentication from the server?

I don’t want reference links from other websites containing elaborate explanations. Just the core of it will do. Generally, how and what is sent from the user so that the server can identify the user? How is certificate based authentication able to replace password based authentication, and how exactly does it work?

I'm answering this based on the TLS v1.2 certificate based client authentication feature. Other protocols may vary in the details.

  Can anybody tell me what is being sent from the user's side for
  getting authentication from the server?

The overhead to a normal handshake consists only of the user's certificate (+ intermediate certificates eventually, really uncommon) and the signature over some previsouly exchanged data.

  Generally, how and what is sent from the user so that the server can
  identify the user?

During the course of a standard TLS handshake a bunch of data is exchanged. This includes the server's certificate, random nonces of both parties and cipher suite negotiation data.
If the server requests a client certificate (which will also include a list of the valid CAs it's going to accept), the client will sign the whole transcript up to this point and will send the signature and the certificate to the server. The inclusion of the nonces prevent re-use of the signature, the inclusion of the server's certificate prevents out-of-context use of the signature and the cipher suite signature prevents downgrade attacks.

  How is certificate based authentication able to replace password based
  authentication, and how exactly does it work?

The server receives the signature and the certificate. It can then verify the correctness of the signature using the public key embedded in the certificate. If the signature is valid, the server knows that the client has the private key belonging to the certificate. As the server can choose the trustworthy CAs himself (including himself), he can trust the CA to have bound the correct public key to the correct person. So he knows that only the person ownging the certificate could have signed this handshake and thereby the client is the person owning the certificate.

This directly authenticates the handshake to the server and there's no need to subsequently send a password for the sake of authentication.


Gaussian distribution over ideal lattices I am reading Lyubashevsky's paper [LPR10] about ideal lattices and R-LWE problem and I did not understand the following part:

"Using the canonical embedding also allows us to think of the distribution
$D_r$ (for $r \in (R^+)^n$) over $H$ as a distribution over $K$. Strictly speaking, the
distribution $D_r$ is not quite over $K$, but rather over the field $K_{\mathbb{R}} = K ⊗_{\mathbb{Q}}\mathbb{R}$,
which, roughly speaking, is to $K$ as $\mathbb{R}$ is to $\mathbb{Q}$."

Can someone please explain this?

The space $H$ is defined such that it is isomorphic to $\mathbb{R}^n$ for some $n$. Therefore, we can choose a basis $\{h_1,\ldots,h_n\}$ such that for every $h\in H$ there exist $x_1,\ldots,x_n\in\mathbb{R}$ such that $$h=x_1h_1+\cdots+x_nh_n.$$
So we think of elements of $H$ as linear combinations of a basis with coefficients in $\mathbb{R}$.

On the other hand, we defined a number field $K=\mathbb{Q}(\zeta)$. As a vector space, this is isomorphic to $\mathbb{Q}^n$ (this $n$ is the same $n$ from above, we simply construct $H$ that way). Choosing a basis $\{k_1,\ldots,k_n\}$, for every $k\in K$ we can find $y_1,\ldots,y_n\in\mathbb{Q}$ such that
$$k=y_1k_1+\cdots+y_nk_n.$$
So we think of elements of $K$ as linear combinations of a basis with coefficients in $\mathbb{Q}$.

The distribution $D_r$ is defined on the space $H$, which has coefficients in $\mathbb{R}$. We could try and apply this to $K$, but the coefficients of $K$ are only in $\mathbb{Q}$. The statement you cite says that we apply $D_r$ to the space which has the same basis as $K$, but with coefficients in $\mathbb{R}$. This space is denoted $K\otimes_\mathbb{Q}\mathbb{R}$.


Why are cryptographically secure hashes required for digital signing (RSA or DSA)? I know that a cryptographically secure hashing algorithm is required for proper message signing (SHA-1, or I think SHA-2 is the current suggested algorithm). However, why does the hashing algorithm necessarily need to be "strong"?

Seeing as the hashing is done before encryption/signature calculation, wouldn't an attacker need to first have the private key of the signer before being able to cause any damage? What sort of vulnerabilities do we open ourselves up to when we use weak hashing algorithms in DSS?

Well, if the hash function is weak, then the attacker might be able to take a valid signature for a signed message, and find a second message for which the signature for this first would also validate for the second.  For example, if Alice signs the message "I like chocolate", what Bob might do is find a second message "Alice owes Bob $13,106,107.57", and reuse the chocolate signature for the second message.

Here's how it works; when someone verifies the signature, they take the message, hash it, and then uses the underlying signature verification on the computed hash, the signature and the public key.  Note that once we have computed the hash, the signature verification logic doesn't pay any more attention to the message. Hence, if Bob can find a second message that hashes to the same value, then the rest of the signature verification logic will proceed as with the valid message.  Note that the attacker didn't need the private key to do this; all he needed was to find a second message that hashed to the same value.

The formal term for the property that a hash function doesn't allow someone to do this is "second preimage resistance"; that is, given an image, one cannot find a second image that hashes to the same value.

Now, it is possible that Bob can get Alice to sign an innocuous message that Bob had picked out (and then reuse that signature with a message that isn't quite so innocuous); because of this, we generally also insist that hash functions has a stronger property called "collision resistance"; that is the property that one cannot find two different images that hash to the same value.


Pairings in Identity-based encryption vs. Attribute-based encryption The bilinear map in Identity-based encryption should satisfy $e(aP,bQ)=e(P,Q)^{a\cdot b}$ whereas Attribute-based encryption schemes use $e(P^a,Q^a)=e(P,Q)^{a\cdot b}$ with $a,b\in\mathbb{Z}_p$ and $e:\mathbb{G}_1\times\mathbb{G}_2\rightarrow\mathbb{G}_T$.

Why are they different and are there reasons to prefer one over the other? Are they fixed in their purpose?

There really isn't a difference. It is just author preference in notation. Some authors prefer to write the pairing operations multiplicatively $e(P^a, Q^b)=e(P,Q)^{ab}$ while others prefer to write it additively $e(aP,bQ)=e(P,Q)^{ab}$.

This comes from the fact that in $e : \mathbb{G}_1\times \mathbb{G}_2\to\mathbb{G}_T$, $\mathbb{G}_1$ and $\mathbb{G}_2$ are (typically) elliptic curve groups, in which the group operation is additive, while $\mathbb{G}_T$ is a multiplicative group. Thus some authors might prefer to make the additive notation of the elliptic curve groups more explicit while other others prefer to make the notation more consistent.


Compact ROM with space only for EdDSA. How to fit a key exchange algorithm inside? I have implemented Ed25519 for a constrained-memory system, and I want to provide a Shared Secret functionality. The recommended method is to use X25519 for this; but then I would have to implement point multiplication over the Montgomery curve Curve25519, which I don't really have room for.
Would there be any downside to using Ed25519 directly for this? In other words, if PrK is my private key and PuK is your public key, our shared secret is [PrK]PuK computed over the curve Ed25519, and not the curve Curve25519. Perhaps then I could hash the result, as Bernstein recommends for X25519.
I am aware of two possible issues: firstly, Curve25519 is slightly faster here; but this is not a serious problem in my application. Secondly, such a custom algorithm is not recommended by any standard; this is a more serious problem, but I can live with it. Does anybody know of any more potential problems with this approach?

A bit of nomenclature first: “Ed25519” is defined to refer to the EdDSA signature algorithm over the edwards25519 curve. What you appear to actually mean is whether you can reuse your edwards25519 code for Elliptic Curve Diffie–Hellman (ECDH).
There is no inherent reason that you can't use edwards25519 for ECDH. We've been doing ECDH with all kinds of curves for ages already, and edwards25519 works just fine as any other. You need to take the same precautions as for X25519, too: multiply by the cofactor $h=8$ or check against a blacklist of bad points (but the encoding of those points will differ between compressed edwards25519 points as for Ed25519 and X25519).
Since you say you're looking at a constrained-memory system, it is likely that you've first built signature verification (which not require constant-time code). If you're going to reuse this code for key exchanges, make sure all curve code and field arithmetic code (except the routines only used signature verification) are made to be constant-time.
A key exchange protocol requires more than just a curve, however, so you may want to look into e. g. the Noise protocol patterns.


ElGamal - What if the Decisional Diffie-Hellmann problem could be solved? I have read that if the DDH problem could be efficiently solved, the IND-CPA would not hold for ElGamal.

I don't see why it makes ElGamal less secure if you have $g^a$, $g^b$ and $g^c$

Let $\mathcal{A}(g^a,g^b,g^c)$ be a DDH adversary which will return 1 if it thinks that $c = ab$, and return 0 if it thinks that $c$ is chosen from random.

Let $a$ is a private key and $g^a$ is a public key, we can attack IND-CPA of ElGamal encryption as follows.

Random $m_0,m_1$ and send them to the challenger.
The challenger will random $b$ and send $(g^b,g^{ab} m_i)$ back, where $i$ is the experiment number.
We can call $\mathcal{A}(g^a,g^b,\frac{g^{ab}m_i}{m_0})$. If it returns 1, we will guess that we are in Experiment 0, but, if it returns 0, we will guess that we are in Experiment 1.

Now we can distinguish between Experiment 0 and Experiment 1 easily.


Why is a prime number used in ECDSA? So I need to write a piece for school about ECDSA and how it is secure. Now I thought I had a simple question, however, I can't seem to find an answer anywhere:

Why does the p in the formula need to be a prime number?

Now I understand how you can only have modular inverses of prime numbers, and I thought maybe that had something to do with it, but I can't see how though.

This is the site where I found the formula from the ECDSA algorithm: https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/

Why does $p$ need to be a prime number?

That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring.

That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently.

More specifically: if $q$ is such that $0<q<p$ and $\gcd(p,q)\ne1$ (which is possible when $p$ is not prime), then there exists no $r$ with $q\,r\equiv1\pmod p$, that is $q$ has no multiplicative inverse. This would invalidate formulas with the term $(x_P-x_Q)^{-1}\bmod p$ when $\gcd(p,x_P-x_Q)\ne1$, as used when performing point addition. With $p$ prime, that can only occur for $x_P\equiv x_Q\pmod p$, which can be handled as a special case in point addition.

  you can only have modular inverses of prime numbers

Uh, no. Counterexamples abound. Say $1$, which is not prime, and is its own modular inverse; and $4$, which is not prime, and has modular inverse $7$ modulo $9$, since $4\times7=3\times9+1$.

Correct formulation: reliable modular inversion requires prime modulus.

More precisely: all integers from $1$ to one less than the modulus have a multiplicative modular inverse if and only if the modulus is prime.

Note: for different (security) reasons, the number $n$ of points on the curve (including the neutral, also known as the point at infinity) needs to be a prime too (as it is in ECDSA), or at least to have a large prime factor.


Message space when using the group of QR's for El Gamal Encryption My textbook states, that the DDH-assumption is not satisfied when we use the group
$\mathbb{Z}/p \mathbb{Z}$ and demonstrates an attack using Eulers Criterion. After that, it states that one should use the group of quadratic residues ($\operatorname{QR}$) over $\mathbb{Z}/p \mathbb{Z}$, where $p=2q+1$ is a safe prime.

I had a look at the El Gamal encryption scheme (which uses the DDH-assumption) and saw, that the message that we want to encrypt has to lie in the group that we choose. If this group is $\mathbb{Z}/p \mathbb{Z} = \{1,2,3,\ldots ,p-1\}$ we can encrypt every message, that is not greater than $p-1$. However, if we use the group of $\operatorname{QR}$'s over $\mathbb{Z}/p \mathbb{Z}$, I think that some messages (namely $(p-1)/2$ many) cannot be encrypted.

If this is true, how would one solve this in practice?

If this is true, how would one solve this in practice?

Actually, in practice, what we generally do is not use El Gamal at all, but instead use Integrated Encryption Scheme (IES), which solves the same problem based on the same hard problem, but where one doesn't worry about Quadratic Residues (or the homomorphic properties, or the need to compute inverses, which is doable but annoying).

Now, if we have to use El Gamal (e.g. because we need to take advantage of the homomorphic properties), well, one way to avoid the QR problem is to simply square the plaintext before encryption (and hence the plaintext that we encrypt is always a QR).  Then, on decryption, we would compute the square root (and take the smaller of the two possible values).  This implies that the plaintext is limited to the range $(0, (p-1)/2)$, but any value in that range can be encrypted.


RSA/DSA: Wouldn't it make sense to sign using decoding the data hash? Why is encoding using the private key used for signing? Wouldn't it make sense to keep the premise, that private is for decoding and public is for encoding? i.e. create a hash and threat it as a result of the crypting and decrypt it. The decrypted value being the "signature". Than when someone want to validate the signature, he would encrypt the signature and he would get the hash.

Am I missing something? Why is this not used?

Your question appears to be "why do we use the terminology 'encoding' when talking about what we do as a part of the signature operation".  Well, we don't (at least, I don't, and I don't remember hearing that terminology from someone else).

As for RSA, well, the terminology you use is moderately irrelevant (as long as you do the cryptographical operations correctly, it doesn't matter what you call them); on the other hand, encoding would appear to imply that you are taking a 'signal', and putting it into a different representation, while decoding would appear to imply that your reversing that operation, and are putting the signal back into its original state.  While I suppose you could call the signature operation an "encoding" one, calling it a "decoding" one would appear to me to be an abuse of the terminology.

AS for DSA, well, your description of "encrypt the signature and he would get the hash" is not how DSA verify works; instead, the verifier inserts the signature, values from the public key and the hash into a formula, and if both sides of the formula are the same value, then the signature verifies.  There's nothing that can be usefully described as "decoding" here.


Assuming your differential uniformity and non-linearity figures are correct, then yes, your s-box is slightly stronger against basic differential and linear cryptanalysis.  Although Anubis already was essentially immune to basic differential and linear cryptanalysis.  However your s-box would need to be evaluated against other forms of cryptanalysis (e.g. interpolation, invariant subspace, etc) in order to determine if it was "better" in a more general sense.  It may also be less efficient in terms of hardware implementation than the current Anubis s-box (to invoke another, no-less crucial sense of "better").

Note: The AES s-box is affine-equivalent to an involution (as will be obvious if you think about the multiplicative inversion function), and has a higher non-linearity and lower differential uniformity.  Non-linearity and differential uniformity are the same for all affine-equivalent permutations.  So that should help address your question about the maximum non-linearity of an involution.


Padding on RSA signature and RSA encryption Why use a random padding on RSA encryption and not on RSA signature?

TL;DR: The security definitions ask for different properties.

The usual security definition for public key encryption, asks you, the attacker, to distinguish which message (out of two) was encrypted and you're seeing the ciphertext of. Obviously you can't succeed at defending in this if you don't randomize, because otherwise an attacker could just encrypt the messages himself and compare the results. Also see our canonical answer for the details.

For signature schemes on the other hand, the usual security definition asks you (the attacker) to find a $(m,s)$-pair (where $m$ is a message and $s$ is its corresponding signature) that you haven't seen before or that you haven't received from the oracle (ie any ressources you're allowed to use). As you can see, there's nothing that would require for randomness in this definition and as such there are fully deterministic schemes with "provable" security, such as RSA-FDH.


Atomic multi-party commitments Alice and Bob publicly choose the messages $M_A$ and $M_B$ and independently sign them (Alice privately signs $M_A$, Bob signs $M_B$).

Now Alice and Bob are looking for a protocol that allows them to:

Make sure the other party's signature is valid (in a malicious adversary model)
Only reveal their own signature if they're guaranteed by the protocol to learn the other party's signature as well (atomic reveal)
Not rely on a trusted dealer

Is there such a protocol possible to construct? Can it be extended to N parties instead of 2? Can it work with an ECDSA signature scheme?

Edit: After researching the topic more and thanks to the answers below, I found out this is commonly known as a (strong) fair-exchange protocol and it's impossible in the two-party setup without a trusted third party. However, optimistic fair exchange protocols are possible and they only rely on a trusted party if one of the participants attempts to cheat.

This can be achieved using fair exchange protocols, which seek to ensure that either Alice and Bob both get what they want or neither of them does.


Is this problem still as hard as discrete logarithm (modified ElGamal)? I am trying to find a vulnerability or proof for the following problem:

ElGamal part.

Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate $h=g^k \mod p$. The public key is $(p, g, h)$ and private key is $k$.

To encrypt message $m\in\mathbb Z_p$, randomly select $r\in\mathbb Z_p$ and publish $(g^r, m\times g^{rk})$.

Additional part

Let $s$ be randomly selected from $\mathbb Z_p$. Publish $k+s$ and $g^{rs}$.

Problem

If we know $k+s$, $g^{rs}$ and public key $(g,g^k, p)$ is it possible to get $k$, $s$ or $g^{kr}$?

I have found this article (Is this problem same as discrete logarithm?) which is similar, but I cannot find a way it could help me with my problem.

Is this construction easily breakable? Can it be proved by transformation to discrete logarithm problem or other crypto problem?

Yes, the system is easily breakable.  We have:

$$(g^r)^{k+s} / g^{rs} = g^{rk}$$

You don't list $g^r$ in your problem statement, however it is in the ciphertext, and so we can assume the attacker knows it.


Understanding hybrid cryptography's concepts: signing and CA After learning about symmetric encryption, public-key encryption, one-way hash, digital signature and digital certificate, I was tasked to think of an imaginary hybrid cryptosystem. I was thinking along the lines of this:

Alice and Bob agrees on a shared private key that is to be used to encrypt (using encryption algorithm like AES) messages
To reach private key agreement, Alice and Bob will use DH
Alice now wants to send the message p to Bob
To ensure that Bob can verify the message p comes from Alice, Alice will sign the message p.
Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message p to a message digest called md1. The message digest md1 is then signed by Alice (using some signing algorithm like RSA). This message digest md1 now contains a digital signature and will be called s
Then, Alice will send both the original message p and the signed message digest s after encrypting them using an encryption algorithm (say AES) using the private key that was agreed upon during DH. Alice also sends the required information in regard to verifying the signature.

Now the message sending process is done. It's Bob's turn to receive the sent packages:

Bob will receive and encrypted original message p and signed message digest s
With RSA, Bob can convert the signed message digest s back to message digest md2
To verify that the message has not been tampered with midway, Bob will now hash using the same hashing algorithm (in this case, SHA-1) from the sent original message p to create another md3
Bob then checks if md3 and md2 are the same or not. If they are, they are from Alice. If they're not, Bob will ignore this message
Bob has now received the original message

I was thinking along the lines of the above, but some points went over my head.

Questions:

Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?
When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects? I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?
The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number pn and its prime generator g. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed pn and g are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?
As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?

You're confusing a lot of things:

  Alice and Bob agrees on a shared private key that is to be used to encrypt

You cannot have a "shared private" key; sharing and keeping things private are opposite terms. That would be called a secret key, as it is kept secret between Alice and Bob (some books confuse these terms as well, but yeah).

  To reach private key agreement, Alice and Bob will use DH

OK, the first statement should come after this second one. And yeah, secret key agreement or establishment.

  To ensure that Bob can verify the message $p$ comes from Alice, Alice will sign the message $p$.

With what key? You've used key agreement using DH and you've specified that you'd use a secret key for encryption.

  Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message $p$ to a message digest called $\mathit{md1}$.

Hashing is typically part of the signature generation and verification operation.

  encrypting them using an encryption algorithm (say AES)

AES is a block cipher, it is not a generic cipher that handles messages of any size, and it isn't CPA secure by itself. This matters because if e.g. you'd use AES CBC, it may fail to padding oracle attacks before you decide to check the signature. This was one of the mistakes of e.g. the early TLS protocols (well, up to 1.2, so this is not the distant past or anything).

  With RSA, Bob can convert the signed message digest $s$ back to message digest $\mathit{md2}$.

There is no rule that retrieval and comparing hashes is part of the verification procedure for signature schemes. Recalculation of the hash is of course necessary, but the verification procedure may have a different way of making sure that the hashes are identical.

  Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?

They agree on it beforehand. The algorithms may be static, depend on a single version number, or be established during a handshake (a la TLS).

  2a. When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects?

The processes are not inseparable but they are commonly linked to each other. Unless you explicitly think of a way to untangle them you're probably OK for both.

  2b. I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?

That depends, as you'd normally use an authenticated cipher or MAC to provide message integrity / authenticity. Those may not use a hash at all.

  The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number $\mathit{pn}$ and its prime generator $g$. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed $\mathit{pn}$ and $g$ are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?

That's not strictly necessary as using different values will lead to an invalid secret. It does make sense to:

Validate that DH was successful before validating messages. Although not strictly required, it will better allow you distinguish between broken key establishment and broken messages.
Include the parameters or parameter names in the above validation.
For particular protocols (ECDH with a P-xxx or Brainpool prime curve) to check the validity of the public key.

But note that if you'd use pre-established parameters that the attacker may not have an attack vector in the first place. It depends on your protocol.

  4a. As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem.

You've also failed to define a key pair for signing / verification, so that should come at no surprise.

  4b. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message.

Incorrect. A CA is used to establish trust in the certificates used, which contain the public key used for signature verification (or, in other protocols, encryption). A CA is not involved in the transport protocol at all, except maybe to validate that the certificates are still valid (CRL / OCSP) at the time that the connection is being established.

  4c. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?

The CA is only involved to let the receiver trust the public key of your certificate. If you can use an out-of-band procedure to trust the public key / certificate then you don't need a CA (you could e.g. use self-signed certificates in that case).

You're still a terrible long way off of defining your own secure transport protocol. Either you should follow a crypto course and practice a lot, or you should use an existing protocol such as TLS.


What is the flaw in this model for homomorphic encryption? Imagine a Field Isomorphism  $g : \mathbb F1 \to \mathbb F2$ given by some $g(x)$

Assume a client is planning to outsource his computations to server, translates every possible $x$ as $g(x)$ and sends to server and once he gets the result he translates g inverse to get the answer.

I know the above is straw man solution for Homomorphic encryption, but am being naive to think of possible problems with such model. One problem I could think of is simple frequency analysis would break the system (but this can be mitigated by coming up padding schemes that retain the homomorphic nature), but what are others?

The catch here is , Most of the current homomorphic encryptions are trying to encrypt the data and perform operations on the encrypted data, but here instead of encrypting it , just the input set is transformed to a another field and such mapping $g(x)$ is kept secret.

The last paragraph of Section 2.3 of Gentry's "easy" intro to homomorphic encryption, I believe, contains an important result which applies to your model.

  Researchers [1, 8] showed that if $\mathcal{E}$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell whether two ciphertexts encrypt the same thing), then $\mathcal{E}$ can be broken in sub-exponential time, and in only polynomial time (i.e., efficiently) on a quantum computer.

Where 1 is Algorithms for black-box fields and their application to cryptography and 8 is Quantum algorithms for some hidden shift problems.

Since your isomorphism is deterministic, this would most definitely apply. Granted, just because it can definitely be broken in sub-exponential time does not mean there is no hope (RSA can be broken in sub-exponential time), you are going to have to give a very good hardness proof to get anyone to use your system.