0
$\begingroup$

I'm writing a project on the advantages and disadvantages of symmetric vs asymmetric cryptosystems. At the moment I am trying to define both systems using mathematical notation. Under the heading "Basic Cryptosystems" I have this:

We can define the cryptogram functionally as \begin{equation} \mathit{C=f(M,K)} \end{equation} It will also be helpful to think of the cryptogram as a family of transformations with one parameter like this \begin{equation} \mathit{C=T_{k}M} \end{equation} The transformation $T_{k}$ applied to the message $M$ produces cryptogram $C$. The operation of the transformation $T$ will depend on which cryptosystem is being used. The index $k$ corresponds to the particular key being used. Assume there are a finite number of keys, each with associated probability $P(T_{k})$. There will then be some discrete statistical process which chooses a transformation from the set $T_{1}, T_{2}, ..., T_{n}$. These transformations have associated probabilities $P(T_{1}), P(T_{2}), ..., P(T_{n})$ respectively. We should also assume a finite number of possible messages $M_{1}, M_{2}, ..., M_{m}$ with associated a priori probabilities $P(M_{1}), P(M_{2}), ..., P(M_{m})$. Once $C$ is received, it can be deciphered with $k$ in order to reveal $M$. This is achieved with a unique inverse transformation $T^{-1}_{k}$ such that $T_{k}T^{-1}_{k}=I$, the identity transformation. So \begin{equation} M=T^{-1}_{k}C \end{equation} The inverse transformation must be unique for every $C$ which can be deciphered with key $k$ to reveal $M$.

My question is: does this definition apply to both symmetric and asymmetric systems? If not, how can I change it to account for asymmetric systems?

thanks

$\endgroup$
1
$\begingroup$

Your definition only covers symmetric encryption since the same "index" $k$ is used in $T_k$ and $T^{-1}_k$ (i.e., encryption and decryption use the same key)

If you want to give a generic definition that covers both types of encryption, you could say that the transformations are $T_k$ and $T^{-1}_{k'}$ and that in the case of symmetric encryption $k'=k$.

$\endgroup$
1
$\begingroup$

I think it covers both symmetric and asymmetric systems. Given a transformation $T_k$, if computing $T^{-1}_k$ is easy then this is a symmetric cryptosystem. On the other hand, if this is difficult than it is an asymmetric one. Note that in this case, we are ''hard-coding'' the key $k$ inside the transformation. Thus we are just given the transformation $T_k$ and not $k$. In fact this is how Diffie and Hellman (and James Ellis) gave a "proof of existence" of public key encrypton

$\endgroup$
1
$\begingroup$

Preliminary on notation: in the question,

  • it seems advisable to change $C=T_{k}M$  to $C=T_{k}(M)$ , and change $M=T^{-1}_{k}C$  to $M={T_k}^{-1}(C)$
  • it is necessary to change $T_{k}T^{-1}_{k}=I$  to ${T_k}^{-1}\circ T_k=I$ , meaning that the function obtained by applying $T_k$ then its inverse ${T_k}^{-1}$ is identity, with $\forall M, {T_k}^{-1}(T_k(M))=M$.

The question separates the notion of key $K$ from the encryption transformation $T_k$ for this key ($k$ became lowercase and seemingly is now an index, perhaps from a space smaller than the space of all $K$). I would say that it could be extended to cover some forms of deterministic asymmetric encryption (like raw/textbook RSA); but that studying the asymmetry and security of such encryption would require additional considerations about the feasibility of computing $T_k$ for arbitrary input knowing $K$ (which would be the public key), when ${T_k}^{-1}$ would only be computable knowing $K'$, with $K'$ computationally impossible to derive from $K$.

As is, the definition only covers that kind of encryption where the output is a function of key and plaintext (only); when encryption often has an additional random input to the encryption function. That's the case in 3DES-CBC or AES-CTR using random IV, and any form of asymmetric encryption that is secure for small messages (like name of a particular students on a public call roll), including secure forms of RSA, and ElGamal encryption. As is, the notation in the question (modeling encryption for a given key as a function of plaintext only) can thus not cover any form of semantically secure asymmetric encryption; which is a huge gap.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.