4
$\begingroup$

I am looking at the Koblitz method for encoding a message as an elliptic curve point. The first step given in the paper I'm reading is:

"Choose an elliptic curve and its associated auxiliary base parameter, k."

I have not heard the term "associated auxiliary base parameter" before. Does it mean the order of the curve, or something else?

$\endgroup$
3
$\begingroup$

Based on a quick Google search, I assume you're reading the paper "Modified Koblitz Encoding Method for ECC" by Kodali and Sarma (Int.J.Rec.Tr.Eng.Tech., vol. 8, no. 1, Jan 2013).

The fact that the paper doesn't actually cite any source for the encoding scheme, or even cite anything by Koblitz, makes me a bit skeptical of the paper's quality. For that matter, so does the fact that they seem to be using tiny curve sizes and encoding individual ASCII characters as curve points. The security levels they seem to be claiming in their last figure also look absurdly low (9 bits, really??), which at least seems honest, if not particularly useful.

All in all, while I admit to only skimming the paper, and that I may have missed some crucial detail, at least at a glance it certainly trips my bullshit detector. I suggest you, at the very least, read it with a highly critical eye.

In any case, I assume that, by "Koblitz's encoding method", they're referring to one of the three encoding schemes described in section 3 of Koblitz's original 1987 paper, "Elliptic Curve Cryptosystems" (Koblitz, N.; Mathematics of Computation 48(177), January 1987, pp. 203–209). It's not 100% clear to me which one they're describing, but I suspect it's most likely the second one, where the plaintext $m$ is mapped to a curve point by multiplying it by some constant $k$ (1,000 in the example) and testing all $mk \le x < (m+1)k$ by brute force to (hopefully) find an $x$ that corresponds to a curve point.

Ps. You may also find these earlier related questions interesting:

Pps. I took a closer look at the Kodali & Sarma paper to see which EC cryptosystem they're actually using, and I couldn't make any sense of it — it looks as if they're effectively just running a symmetric Caesar cipher over an elliptic curve (after first doing ECDH key agreement). If so, that still makes absolutely no sense to me; it's not semantically secure, and anyway they'd be much better off just feeding the ECDH secret (computed over a secure curve, not the tiny one they seem to be using) to a KDF and using it to key a standard symmetric cipher, like normal people do.

$\endgroup$
  • $\begingroup$ Oh of course ECIES is the way to go. But this is academic I am just trying to learn how it works. and how to implement it. $\endgroup$ – colobusgem Mar 4 '15 at 13:08
  • $\begingroup$ Also the method decodePoint here docjar.org/docs/api/org/bouncycastle/math/ec/ECCurve$Fp.html, what is this method doing? case case 0x03 seems to look a bit like method 2 in Koblitz's paper. $\endgroup$ – colobusgem Mar 4 '15 at 15:15
  • 1
    $\begingroup$ @colobusgem There are serious academic papers and pseudo (crappy) academic papers. The one you are looking at seems to fall in the latter category ;) $\endgroup$ – DrLecter Mar 4 '15 at 19:12
  • $\begingroup$ That makes sense. Either way I have managed to implement what I think is algorithm 2 from koblitz's paper in java and have found that (obviously) some integers can easily be encoded on to a point, and others not so much. Is there a way to figure out the probability an integer will be successfully encoded before starting out and brute forcing all possible x's? Also on a probability note: I assume it is better to randomly select from the pool of possible X's as opposed to starting at the lowest and working up to the highest. $\endgroup$ – colobusgem Mar 5 '15 at 16:34

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.