KevBurnsJr

I used to be this guy.

I want a short alphanumeric hash that’s unique and who’s sequence is difficult to deduce. I could run it out to md5 and trim the first n chars but that’s not going to be very unique. Storing a truncated checksum in a unique field means that the frequency of collisions will increase geometrically as the number of unique keys for a base 62 encoded integer approaches 62^n. I’d rather do it right than code myself a timebomb. So I came up with this.

I’ll walk us through the finer points below.

class PseudoCrypt {
 
	/* Next prime greater than 62 ^ n / 1.618033988749894848 */
	private static $golden_primes = array(
		1,41,2377,147299,9132313,566201239,35104476161,2176477521929
	);
 
	/* Ascii :                    0  9,         A  Z,         a  z     */
	/* $chars = array_merge(range(48,57), range(65,90), range(97,122)) */
	private static $chars = array(
		0=>48,1=>49,2=>50,3=>51,4=>52,5=>53,6=>54,7=>55,8=>56,9=>57,10=>65,
		11=>66,12=>67,13=>68,14=>69,15=>70,16=>71,17=>72,18=>73,19=>74,20=>75,
		21=>76,22=>77,23=>78,24=>79,25=>80,26=>81,27=>82,28=>83,29=>84,30=>85,
		31=>86,32=>87,33=>88,34=>89,35=>90,36=>97,37=>98,38=>99,39=>100,40=>101,
		41=>102,42=>103,43=>104,44=>105,45=>106,46=>107,47=>108,48=>109,49=>110,
		50=>111,51=>112,52=>113,53=>114,54=>115,55=>116,56=>117,57=>118,58=>119,
		59=>120,60=>121,61=>122
	);
 
	public static function base62($int) {
		$key = "";
		while($int > 0) {
			$mod = $int-(floor($int/62)*62);
			$key .= chr(self::$chars[$mod]);
			$int = floor($int/62);
		}
		return strrev($key);
	}
 
	public static function udihash($num, $len = 5) {
		$ceil = pow(62, $len);
		$prime = self::$golden_primes[$len];
		$dec = ($num * $prime)-floor($num * $prime/$ceil)*$ceil;
		$hash = self::base62($dec);
		return str_pad($hash, $len, "0", STR_PAD_LEFT);
	}
 
}

Here’s a use case

$ids = range(1,10);
foreach($ids as $id) {
  echo PseudoCrypt::udihash($id) . "\n";
}

cJio3
EdRc6
qxAQ9
TGtEC
5ac2F
huKqI
KE3eL
wXmSO
YrVGR
BBE4U

Pretty random-looking, huh?

Base 62

Hashes are base 62 encoded base 10 integers. 1=1, 10=a, 36=Z, 61=z, 62=10, 72=1a, etc.

62, 3844, 238328, 14776336, 916132832, 56800235584, 3521614606208

1 character = 62 permutations, 2 characters = 3844 permutations, etc.

41, 2377, 147299, 9132313, 566201239, 35104476161, 2176477521929

41 = next highest prime from golden mean of 62.
2377 = next highest prime from golden mean of 3844.

Uniqueness

I chose to use primes to ensure hash uniqueness. Any prime greater than one half 62^n will do, but if you use a prime near 62^n or 62^n/2 or 2*62^n/3 etc, you will detect a linearity in the sequence at certain points in the ring.

Appearance of randomness

I chose primes near the golden ratio to maximize the appearance of randomness. Given a small set of hashes (even with the associated id) it would be difficult for anyone to guess the next hash.

This is a minimum security technique.

Keep your primes a secret and limit the number of hashes a user can get his hands on to make it harder for script kiddies to reverse engineer your algo. This is a thin rotation and base re-encoding obfuscation algorithm, not an encryption algorithm. Don’t use this to crypt sensitive info. Use it to obfuscate integer IDs.

Tools Used

Golden Ratio Calculator
Prime Numbers Generator

That’s it.

Any of you CS majors out there care to tell me what the technical term is for this type of hash?

Rails uses timestamp, so I will too. Here’s a nice little matrix I found.

http://jmmolina.free.fr/t_49552/MySQL%20Date%20and%20Time%20Types.pdf

Solution:

sudo apt-get install libxml2-dev

While this example may be a good illustration of a one-to-many relationship, it’s also a good way to get punched in the face.

For example if You have Husband and Wife model. Husband has one Wife and Wife belongs to Husband. In that case Wife must contain husband_id column because she belongs to Husband. From other hand Husband don’t have to contain any foreign key, because he is a base model and his Wife knows that she belongs to him.

For any SOAP web service, you are very likely to find a WSDL which describes the service.

WSDL is an XML format for describing network services as a set of endpoints operating on messages containing either document-oriented or procedure-oriented information.

However, WSDL 1.1 is really not designed to describe RESTful web services. WSDL 2.0 includes language for better describing RESTful web services, but is still only a recommendation.

So suppose I wanted to automatically generate a JavaScript api for interacting with an arbitrary RESTful web service. I should be able to find an appropriate WSDL, parse the described resource types along with their properties, relationships and urls, create some internal model of the web service based on the properties of those resources and generate some JavaScript classes for interacting with the web service.

This is a rather simplistic example, but it shows what a partial service description might look like …

<service name="Twitter">
  <base href="http://twitter.com"/>
  <resources>
 
    <resource class="User">
      <base href="/users">
      <properties>
        <property name="id" type="int" />
        <property name="screen_name" type="string" />
      </properties>    
      <relationships>
        <relationship type="HasMany" target="Status">
      </relationships>
      <method name="GET"></method> #get user info
      <method name="POST">         #create new user
        <requires type="property" name="screen_name" />
      </method>
      <method name="DELETE">       #delete user
        <requires type="auth" name="owner" />
      </method>
    </resource>
 
    <resource class="Status">
      #...
    </resource>
 
    #...
 
  </resources>
</service>

After parsing this document in Javascript, I should be able to create a set of JavaScript classes that behaves somewhat like this …

Resource.load('http://twitter.com/service-description.wsdl', 'Twitter')
Resource.model('Twitter', 'User');
 
// GET a user's details
var user = Twitter.User.find('123');
var screen_name = user.screen_name;
 
// GET a user's most recent status update
Resource.model('Twitter', 'Status');
var most_recent_update = user.Status.last();
 
// POST a new status update on a user's behalf
var new_status = user.Status.new();
new_status.status = "Look ma, no library!";
user.Status.post(new_status);

Seems pretty powerful, huh?

But if you go to Twitter’s API documentation, you will not find any such machine-readable service description document. Nor does the markup for the plain-text description of the service contain any semantic markup that could be used to generate such a description document.

So why doesn’t Twitter post a machine-readable description of their web service? Are they just dumb?

Well, probably not.

I did about 2 days of digging around and finally came across the following article which leads to many additional articles on the subject (thanks to Bradley Holt in #REST on irc.freenode.net) …

Debate: Does REST Need a Description Language

… and this very succinct conclusion from Mark Baker

REST, WADL, forest, trees

So if you’re writing (or generating) contract/interface-level code which can’t late-bind to all resources, everywhere, you’re not doing REST [...]

Cut the cord already! RPC is dead. You’re not in Kansas anymore.

So if we’re not in Kansas, then where does that put us?