Koblitz encoding a message to a point, what is the "associated auxiliary base parameter"? 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?
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&ndash;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 &lt; (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:


Mapping of message onto elliptic curve and reverse it?
Fast hashing into elliptic curve


Pps. I took a closer look at the Kodali &amp; Sarma paper to see which EC cryptosystem they're actually using, and I couldn't make any sense of it &mdash; 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.