When I wanted to start a Rails application on a machine (Ubuntu) with a new Ruby installation I got this error. After I read posts where it was suggested to install libopenssl-dev and recompile Ruby I found this suggestion and installing libopenssl-ruby fixed it.