Drupal 7 adding rel to the href's of Login and Registration
Yes you could spend time tearing apart templates, and hacking in the required code, I would say the cleaner, 'more drupal' solution would be to use a combination of


Menu and menu items
The module menu attributes


From the project page:


  This simple module allows you to specify some additional attributes
  for menu items such as id, name, class, style, and rel.